Priority Queue/Heap

힙은 완전이진트리구조

Max Heap -> 부모 노드의 data가 자식 노드의 data보다 크거나 같다.

Min Heap -> 부모 노드의 data가 자식 노드의 dta보다 작거나 같다.

 

힙은 Array 기반으로 구현한다.

완전이진트리구조이므로 index를 통해 부모노트 자식노드로 바로 접근이 가능하다.

 

왼쪽 자식 노드: 2n

오른쪽 자식 노드: 2n+1

부모 노드: n/2

 

push O(1)

1. 맨 마지막 index에 데이터를 추가한다.
2. 부모 노드와 비교하여 부모 노드보다 크다면(작다면) swap한다.
3. 부모 노드보다 작을(클)때까지 반복한다.

pop O(log n)

1. Root node를 꺼낸다
2. 맨 마지막 index의 값을 Root Node로 가져온다.
3. 현재 root node의 값이 Max(Min)을 만족하는지 자식 노드들과 비교한다.
4. 자식 노드가 작을(클)때까지 반복