-
- Heap은 Complete Binary Tree를 기본으로 가지는 자료구조
- 일반적으로 array로 구현하는 것이 좋음
- Heap 은 최댓값 또는 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안됨
- 시간복잡도: O(log₂N)
- Heap은 다음과 같은 속성(property)를 만족함
- A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대소관계가 성립
- 종종 priority queue를 보충하는대에 사용
종류
max heap: root노드가 가장 큰 수
min heap: root노드가 가장 작은 수
Max Heap
부모노드의 키가 자식노드의 키보다 항상 큼
Node Insertion
max heap에서 노드 추가는 말단의 맨 오른쪽의 leaf node에 자리를 하나 만들고 해당 노드에 값을 대입한 다음 parent node와 값을 비교하며 자리를 바꿔 나감. (root node 까지)
Node Deletion
max heap에서 노드 삭제는 항상 루트노드를 지움. 그 다음 complete binary tree를 유지하기 위해 tree를 재조정함. 말단의 맨 오른쪽 노드를 지운 다음, 루트 노드 자리에 옮기고 child node와 비교해 자리를 바꿔나감.
Max Heap에서 노드 추가, 삭제는 모두 트리의 depth만큼 걸림 -> O(log₂N)
Min Heap
부모노드의 키가 자식노드의 키보다 항상 작음
키의 대소관계는 오로지 부모노드와 자식노드 간에만 성립되며, 형제(sibling) 사이에는 대소관계가 정해지지 않음
Priority Queue
일반적인 queue는 FIFO 이기 때문에 먼저 들어온 데이터가 먼저 나가지만, priority queue는 우선순위가 높은 데이터 먼저 나감
새로운 노드가 삽입되면 우선순위에 맞는 위치에 삽입 (enqueue)
제거할 때는 우선순위가 가장 높은 맨 앞의 노드를 삭제 (dequeue)
