힙 정렬(heap sort) <priority queue> C++

min heap 구현

 

heap[i]의 값은 heap[i * 2] 와 heap[i*2 + 1]의 사이에 있다

BST(이진 탐색 트리)구조를 기반으로 한다

 

STL의 priority queue를 사용하면 되므로 직접 구현할 일은 없겠지만

heap 자료구조를 직접 구현해 본다는 점에서 의미있다.

#include <iostream>
#include <vector>
using namespace std;
 
vector<int> heap;
 
void push_heap(vector<int>& heap, int newvalue){
    heap.push_back(newvalue);
 
    int idx = heap.size() - 1;
    while(idx > 0 && heap[(idx-1)/2] < heap[idx]){
        swap(heap[idx], heap[(idx-1)/2]);
        idx = (idx-1)/2;
    }
}
 
void pop_heap(vector<int>& heap){
    heap[0] = heap.back();
    heap.pop_back();
    int here = 0;
    while(true){
        int left = here*2 + 1, right = here*2 + 2;
        if(left >= heap.size()) break;
 
        int next = here;
        if(heap[next] < heap[left]){
            next = left;
        }
 
        if(right < heap.size() && heap[next] < heap[right]){
            next = right;
        }
        if(next == here) break;
        swap(heap[here], heap[next]);
        here = next;
    }
}