C++ : STL heap

#include <algorithm>

---

index로 임의 접근이 가능한 자료구조라면 STL heap 관련 함수 적용 가능 : arr, vector

​

1. make_heap(배열.begin(), 배열.end() , 생략가능 less<>) : O(N), max 3N (???)

새로운 자료구조로 생성되는게 아니라, 기존 배열을 힙 정렬 형태로 재배열하는 형태로 힙을 구성한다. 기본 max heap으로 정렬된다. greater functor로 min heap 정렬도 가능하다.

2. pop_heap(배열.begin(), 배열.end()) : O(logN), max logN

재배열 후 [0] 이 head가 된다. pop_head는 head를 맨 마지막 인덱스와 뒤바꾸고, 맨 마지막 인덱스 전까지를 다시 heap 형태 재정렬해준다. vector를 사용하는 경우 back()으로 값을 백업하고 pop_back으로 제거하면 된다.

3. push_heap(배열.begin(), 배열.end()) : O(logN), max 2logN

맨 마지막 인덱스가 새로 들어갈 노드라고 가정하고, 맨 마지막 인덱스 값을 힙에 추가하는 형식으로 재배열한다. 즉 push_heap 앞에는 push_back 등으로 마지막에 새로운 값을 넣어주어야 한다는것.

4. sort_heap(배열.begin(), 배열.end()) : O(NlogN), max NlogN

배열 전체를 힙 형태로 싹 갈아엎는다.