[자료구조] 힙(Heap) / 우선순위 큐

[ Heap의 정의 ]

우선순위 큐를 구현한 완전 이진트리로 최댓값 혹은 최솟값을 빠르게 찾아내기 위한 이진트리.

높이가 작은 곳부터, 왼쪽부터 삽입하는 방식으로 작동하며 느슨한 정렬 상태를 유지합니다.

종류로는 최소힙, 최대 힙이 있습니다. 위의 그림은 최소 힙을 나타내었습니다.

• 최소 힙(Min Heap) : 부모 노드의 값이 자식 노드보다 작다.
• 최대 힙(Max Heap) : 부모 노드의 값이 자식 노드보다 크다.

Heap은 이진 탐색 트리(Binary Search Tree)와 비슷한 트리이지만, 자식과 부모 사이의 대소관계가 다릅니다. Heap은 중복값을 허용, 이진 탐색 트리는 중복값을 허용하지 않습니다.

 

Heap에서 할 수 있는 것은 이진 탐색 트리에서도 가능한데 힙을 쓰는 이유가 무엇일까요?

• Heap으로 구현 가능한 것은 균형 이진트리에서도 가능 한것이 맞고, 시간복잡도도 O(logN)으로 동일합니다.
• 그러나 Heap은 균형 이진 트리보다 수행 속도가 빠르고, 공간을 적게 차지합니다.
• 그러므로 최소/ 최대 값의 확인 및 삭제가 필요할 때는 Heap을 사용하는 것이 더 좋습니다.

 

[ 힙의 특징 ]

• 성질: 최대/ 최소 원소를 빠르게 찾을 수 있습니다.
• 완전 이진 트리(Complete binary tree)

 

[ 힙 연산 ]

연산은 모두 최소힙을 예시로 들었습니다.

 

삽입 연산

• 시간 복잡도 : O(logN)

삽입연산1

힙에 새로운 요소가 들어오면 새로운 노드를 힙의 마지막 노드로 삽입합니다.

만약에 새로운 요소가 부모 노드 보다 작다면 위치를 교환하여 최소 힙의 성질을 만족시켜 줍니다.

3번째로 들어온 3이 부모 값인 5보다 작으므로 위치를 교환합니다.

삽입연산2

새로운 요소가 들어와 부모노드와 교환을 하고 난뒤에도 부모노드보다 작다면, 또 교환을 해줍니다.

마지막으로 들어온 1은 부모노드인 5보다 작으므로 교환을 해주었습니다.

교환한 상태에서 1은 부모노인 2 보다 작으므로 다시 교환을 하여 1은 루트 노드의 위치에 가게 됩니다.

 

 

삭제 연산

• 시간 복잡도 : O(logN)
• 힙에서의 삭제 연산은 힙의 최대값, 최솟값을 삭제합니다.

다음과 같이 힙이 있을 때 최솟값인 1을 삭제 연산을 하게 된다면 힙의 구조가 깨지게 됩니다.

그래서 힙의 삭제는 마지막 노드(5)와 부모노드(1)를 교환한 후에 삭제를 진행합니다.

교환하고 삭제한 후에 힙의 성질을 만족시키기 위해 부모-자식 노드간의 비교를 하여 교환하여 줍니다.

1) 최소 값인 1을 삭제하고 마지막 노드(5)를 루트 노드에 올립니다.

2) 루트 노드(5)와 자식 노드를 비교하여 더 작은 노드(2) 와 교환합니다.

 

힙 구현(STL)

• C++ STL에 힙이 있습니다. 이름은 priority_queue입니다.

#include <queue>
priority_queue<int, vector<int>, greater<int>> pq; //min_heap
//default는 less<int> -> max_heap
pq.push(1);    //1을 추가
pq.top();    //최소값을 반환
pq.pop();    //힙의 최소값을 삭제