[자료구조] 힙(Heap)

우힙힙힙 ^ㅇ^ 우히히 좌히히(웃기다!)

 

힙

- 완전이진트리이면서, 모든 노드의 key값이 각 자식노드들의 key값보다 크거나 작은 heap property를 지키는 자료구조

- heap property가 부모가 자식보다 큰 것인 경우 Maxheap이 되고, 작은 것인 경우 Minheap이 된다.

- 주로 Priority queue로 사용된다.

- 완전이진트리여야한다는 점에서 array로 구현이 용이하다. (i, 2i, 2i+1)

 

삭제 (O(logn)-최악 theta(logn), 최선 theta(1))

1. root를 제거한다.

2. 마지막 노드를 root로 옮긴다.

3. heap property에 맞게 Percolate down한다. - 최대 logn 회의 교환이 일어난다.

* Percolate down : 자식노드와 비교하여 heap property에 맞지 않는 경우 swap

 

삽입 (O(logn)-최악 theta(logn), 최선 theta(1))

1. 마지막 노드에 삽입한다.

2. heap property에 맞게 Percolate up한다. - 최대 logn 회의 교환이 일어난다.

* Percolate up : 부모노드와 비교하여 heap property에 맞지 않는 경우 swap

 

buildHeap

1. 자식 노드가 있는 모든 노드들에 대해((length-2)/2번 노드부터 0번 노드까지)

2. percolate down

- 시간복잡도는 theta(n)이다.

 : 수행되는 n/2회의 percolate down을 모두 합쳤을 때