Module 6 - Heaps

(binary) heaps.

Binary heaps are the most common type of heap. 

Heap 의 중요 요소 = completeness. 

왜 heap 을 쓸까요?

아이템들을 위에서부터, 작은순서, 큰순서로 정렬하고 싶을때 매우 유용, 최대 최소값을 찾기 쉽겠죠?

complete

MinHeap = parent smaller than children / root is min
MaxHeap = parent bigger than children / root is max

• array 로 변환시 위에서 levelorder 로 변환
• left child = 2 * n right child = 2 * n + 1 parent = n/2 
• index size = last data 

언제 쓰지?

accessing the root

priority queue - emergency room waitlist (O(1) to find highest element)

 

heap operation

shape first order next 

ADD

1. completeness 유지를 위해 오른쪽 끝에 더한다
2. - 그 후 heapify 을 통해 큰수 작은수 비교해서 정렬한다 
3. time complexity - O(log n) / O(1) - best case 정렬이 필요없을때

REMOVE

1. 오른쪽 끝 element 와 root 를 바꾼 후 삭제한다 (원래 root)
2. 새로운 root 를 down heap 하며 정렬한다. child 둘다 크다면 더 큰수와 swap 한다.
3. time complexity - O(log n)

Build Heap Algorithm

root = index 1

last element = size index

parent of the last element = size / 2

마지막 subtree 부터 돌아가면서 parent 랑 비교하며 heapify

down heap = o(log n)

num of down heap operation = n / 2

 

구현 ---