힙(Heap)에 대한 간략정리와 C++ 관련 라이브러리 및 함수

완전이진트리 구조에 키값 관련 조건이 있는 자료구조.

완전이진트리?
마지막 레벨을 제외한 모든 노드는 완전히 채워져있으며, 마지막 레벨의 노드는 가능한 좌측부터 시작하는 구조

키 값 관련 조건?

2가지 중 하나가 성립해야한다.

1. 최대 힙 조건

부모노드의 키값이 자식노드의 키값보다 항상 크거나 같다

2. 최소 힙 조건

부모노드의 키값이 자식노드의 키값보다 항상 작거나 같다

주의 : 형제 사이는 대소관계가 존재치 않는다.

 

왜 써요?

"우선 순위"가 고려된 배치이기 때문이다.

이에 앞서 스택과 큐를 생각해보자. 스택은 LIFO, 큐는 FIFO의 법칙에 따라 데이터가 나간다.

우선순위 큐는 '우선순위' 높은 놈이 먼저 나가는 방식인 것.

위의 이미지의 root를 보면, 항상 우선순위가 제일 높던가, 가장 낮던가라는 사실이 보장됨이 확인가능하다.

이러한 성질로 인해, 우선순위 큐를 구현할 때 배열, 연결리스트로도 구현이 가능하지만 힙으로 구현하는 것이 제일 성능이 좋다. 

 

C++ STL Heap

#include <algorithm>

vector<int> v = {1,6,5,2,3,8,4,9,7};
make_heap(v.begin(),v.end());			//우선순위 큐 9 7 8 6 3 5 4 2 1 생성
//값 추가
v.push_back(10);
push_heap(v.begin(),v.end());			//힙에 직접 값을 뒤에 넣고, push_heap을 통해 재배열. 10 9 7 8 6 3 5 4 2 1 변경됨
                                        
//값 내보내기
pop_heap(v.begin(),v.end());			//우선순위가 가장 높은 root node가 pop되고 재배열
v.pop_back();							//이후 직접 값을 pop

최초 make_heap의 경우, level마다 순차적으로 삽입하게된다면 O(nlogn)이나,

Healify(Sift Down)을 통해 시간복잡도를 O(n)까지 낮춘다. 즉 재배열 과정을 힙 생성에 그대로 적용한다는 이야기로 이해하면 될 것 같다.

원소 값 하나에 따른 재배열은 level마다 비교 및 swap이 일어나기 때문에 값 추가 및 내보내기는 O(logn)의 시간 복잡도를 가진다.

 

C++ STL Priority Queue

내부적으로 Heap 자료구조를 통해 우선순위 큐를 구현한다고 함.

기본적인 push, emplace, top, pop, empty, size, ... 다 queue와 비슷하게 작동한다고 보면 된다. 

#include <queue>

priority_queue<int> pq;		//우선순위 큐 생성. 기본설정은 내림차순
pq.push(int);				//원소 삽입. 알아서 정렬된다.

priority_queue<int,vector<int>,greater<int>> pq;	//오름차순 <자료형, 구현체, cmp>

sort의 커스텀 비교 함수와 반대로 작동하는 모습이다.

algorithm의 sort는 인자의 '왼쪽' 기준이지만, 우선순위 큐의 sort는 인자의 '오른쪽'이 기준이 되기 때문!