부모노드의 값이 자식노드보다 항상 크거나 같은 heap → max heap
부모노드의 값이 자식보드보다 항상 작거나 같은 hep → min heap
Questions
높이가 h인 heap의 최대 원소 개수와 최소 원소 개수는?
<aside> 🅰️ 높이 = 0 → 최대 node = $2^1-1$ = 1개, 최소 node = 1개 높이 = 1 → 최대 node = $2^2-1$ = 3개, 최소 node = 2개 높이 = 2 → 최대 node = $2^3-1$ = 7개, 최소 node = 4개 $\therefore$ 최대 원소의 개수 = $2^{h+1} -1$ 개 최소 원소의 개수 = $2^h$ 개
</aside>
원소의 수가 n개인 heap의 높이는 $\lfloor log_2n\rfloor$ 개가 됨을 증명하라
<aside>
🅰️ 위의 내용에 의하여 다음과 같은 식을 추론할 수 있다.
$2^h ≤ n < 2^{h+1}-1$
위의 식에 log를 취해주면
$h≤log_2 {n}<h+1$
$\therefore h = \lfloor log_2n\rfloor$
</aside>
Max heap 의 모든 subtree에서 root node의 값은 그 subtree의 나머지 원소들보다 크거나 같음을 증명하시오
<aside> 🅰️ 귀납적 증명으로 설명 가능
</aside>
Max heap에서 모든 원소가 서로 다를 때, 가장 작은 원소는 어디에 존재하는가?
<aside> 🅰️ leaf node에 존재함
</aside>
내림차순으로 정렬된 배열은 Max heap 인가?
<aside> 🅰️ $a[i]$의 자식 노드 → $a[2i+1], a[2i+2]$ $a[i] > a[2i+1], a[i] > a[2i+2]$
</aside>
원소의 수가 n개인 heap을 tree 구조로 나타내었을 때, $k≥\lfloor \frac{n+1}{2} \rfloor$ 이면 k번째 node는 leaf임을 증명하시오
<aside> 🅰️ k 가 leaf node가 아니라면 자식 노드가 있음. k의 자식노드 = $a[2k+1]$ ← 최소 1개이기 떄문에 왼쪽 노드로 설정 $2k+1 \ge 2 \times \lfloor \frac{n+1}{2} \rfloor > 2 \times \frac{n-1}{2} + 1$ $(x-1 < \lfloor x \rfloor ≤ x$ 에 의하여) 그러나 $2 \times \frac{n-1}{2} + 1 = n$ 이기 때문에 $k ≥ n$ 모순 발생 (heap에는 0~(n-1) 까지만 있음. k는 존재X) $\therefore k$ 는 리프노드
</aside>
Heap은 배열의 일부. 배열 전체가 heap일 필요는 X
