Practice #5
Coddy의 힙 & 우선순위 큐 - 자료구조 시리즈 #7 코스 레슨 — 14개 중 14번째.
챌린지
쉬움정수 배열 arr를 인자로 받아 해당 배열이 유효한 최소 힙(min-heap)을 나타내는지 여부를 반환하는 함수 isMinHeap을 작성하세요.
배열이 최소 힙이 되려면 모든 부모 노드가 자식 노드보다 작거나 같아야 합니다. 구체적으로, 범위 내의 모든 인덱스 i에 대해 arr[i] <= arr[2*i + 1](왼쪽 자식이 존재하는 경우) 및 arr[i] <= arr[2*i + 2](오른쪽 자식이 존재하는 경우)를 만족해야 합니다.
빈 배열과 요소가 하나인 배열은 정의에 따라 최소 힙입니다.
반드시 MinHeap 클래스를 사용해야 합니다 (minheap.<ext>에 제공됨). 결과를 계산하기 위해 sort, slice 또는 표준 라이브러리의 힙 라이브러리와 같은 언어 내장 기능을 사용하지 마세요.
직접 해보기
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "solution.h"
int main() {
char line[8192];
if (!fgets(line, sizeof(line), stdin)) line[0] = '\0';
int arr[4096];
int n = 0;
char* tok = strtok(line, " \t\r\n");
while (tok) { arr[n++] = atoi(tok); tok = strtok(NULL, " \t\r\n"); }
bool r = isMinHeap(arr, n);
printf("%s\n", r ? "true" : "false");
return 0;
}
