[자료구조] Binary Heap(히프)와 Priority Queue(우선순위 큐) - CS면접 대비

이번 글에서는 우선순위 큐(Priority Queue) 구현을 위해 사용되는 이진 히프(Binary Heap)에 관한 내용을 정리해보고자 한다. 일반적인 배열로 우선순위 큐를 구현하는 경우 삽입에 O(N) 정렬에 O(log N) 시간이 소요되는 반면, 히프로 구현하는 경우 enqueue와 dequeue 연산을 O(log N) 시간에 가능하게 해준다.

---

이진 히프(Binary Heap)

---

[1]  최대/최소 히프의 정의

• 최대 히프(max heap)는 최대 트리(max tree)*이면서 완전 이진 트리(complete binary tree)이다.
• 최소 히프(min heap)는 최소 트리(min tree)*이면서 완전 이진 트리(complete binary tree)이다.
• * 최대(최소) 트리 : 각 노드의 키 값이 (자식이 있다면) 그 자식의 키 값보다 작지(크지) 않은 트리이다.

히프는 그 정의에 따라 항상 완전 이진 트리이기 때문에 배열로 표현이 가능하다. 편향 이진 트리와 달리 공간의 낭비가 생기지 않기 때문이다.

---

[2] 최대/최소 히프 삽입/삭제 연산

 

(1) 삽입 연산 : O(log N)

 

 최대/최소 히프에서 데이터를 삽입할 때는 트리의 새 노드(리프)에 삽입한 후 루트 쪽으로 올라가는(bubbling up)방법을 사용한다. 다시 말해, 최대 히프에 삽입되는 원소는 트리의 끝에서 시작해 삽입 후 최대/최소 히프가 되는 것이 확인될 때까지 위치를 바꿔가며 올라간다. 

 삽입 연산의 시간복잡도는 O(log N) 이며, 이는 O(N)이 소요되는 배열이나 연결리스트 방식에 비해 효율적이다. 아래의 예는 [7, 16, 49, 82, 5, 31, 6, 2, 44] 를 차례로 최대 히프로 구현한 우선순위 큐에 삽입한 후의 모습이다.  

최대 히프 우선순위 큐 삽입의 예시

 

(2) 삭제 연산 : O(log N)

 

 최대/최소 히프에서 데이터를 삭제할 때는 히프의 루트에서 삭제한다. 이후 최대/최소 히프를 유지하기 위해(최대/최소 트리이자 완전 이진 트리) 히프의 맨 끝에 위치한 원소를 루트로 옮겨, 최대/최소 히프가 확인 될 때까지 그 자식과 값을 비교해 위치를 결정해준다. 이 때, 최대 히프의 경우 두 자식 중 큰 값을 가진 자식과 값을 비교하고, 최소 히프의 경우 두 자식 중 작은 값을 가진 자식과 값을 비교한다.

 삭제 연산의 시간복잡도는 O(log N) 이며, 이는 O(1) 이 소요되는 배열이나 연결리스트 방식에 비해 다소 느리다. 그러나 삽입 연산에서 히프가 더 좋은 성능을 보이기 때문에 우선순위 큐는 히프 구조로 구현하는 경우가 많다. 아래의 예는 우선순위 큐 [82, 49, 31, 44, 5, 16, 6, 2, 7] 에서 삭제 연산을 두번 수행한 모습이다.

최대 히프 우선순위 큐 삭제의 예시