[코딩테스트] 2-1. 힙(Heap)

힙(Heap) ?

완전 이진 트리 자료구조의 일종

최소(min heap)/최대(max heap)원소를 빠르게 꺼낼 수 있는 자료구조

 

연산 

- 힙 구성(heapify) : heap의 모양 만들기  O(NlogN)

- 삽입 (insert) : 최소, 최대 유지하도록  O(logN)

- 삭제 (remove) :  min heap이면 최소, max heap이면 최대 원소를 꺼내서 없애고 모양 유지  O(logN)

 

min / max heap 예시

- 완전 이진 트리(complete binary tree)로 구현하는 것이 일반적

ㄴ배열을 이용해서 구현 가능함

 

힙의 응용

- 힙정렬 (heapsort) : 임의의 수들이 주어졌을 때, 빈 heap을 만들어 모든 원소 삽입 후 빌 때까지 remove하면 

NlogN에 비례한 시간에 정렬 완료 

- 우선 순위 큐 (priority queue)를 heap를 이용해 구현이 가능하다. (리스트를 이용해서도 구현 가능)

 

코드로 구현

- heap의 헤더파일은 <algorithm>에 정의되어 있다.

- priority queue의 헤더파일은 <queue>에 정의 되어 있다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

void printV(vector<int> vec) {
    for (auto v: vec) {
        cout << v << " ";
    }
    cout << endl;
}

int main() {
    vector<int> vec{1, 6, 5, 2, 3, 8, 4, 9, 7};
    cout << "1. VEC: ";
    printV(vec);

    cout << "2. make_heap VEC: ";
    make_heap(vec.begin(), vec.end());
    printV(vec);

    priority_queue<int> pq;
    priority_queue<int, vector<int>, greater<>> pq1;
    for (auto v: vec) {
        pq.push(v);
        pq1.push(v);
    }
    cout << "3. priority_queue VEC: ";
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;

    cout << "4. priority_queue greater VEC: "; //오름차순
    while (!pq1.empty()) {
        cout << pq1.top() << " ";
        pq1.pop();
    }

    return 0;
}