[DS] Heap?

[DS] Heap

힙이란 무엇일까?

알고리즘에 있어서 아주 중요한 자료구조이다.

알고리즘에서 가장 중요한 것 2가지는 `시간`과 `공간`의 복잡도이다. (Time & Space Complexity)

(최대 or 최소 값을 구하는 문제에서) 힙은 이 두가지 중에서 `시간 복잡도`를 획기적으로 줄여주는 자료구조이다.

[Time Complexity]

Search Max/Min: O(1)

Insert: O(logN)

Remove: O(logN)

최소 or 최대 값은 항상 루트 노드에 존재하기 때문에 O(1) 만에 찾을 수 있다.

힙은 완전 이진 트리 형태를 가지고 있다.

삽입은 가장 마지막 노드 위치에 하며, 

삽입을 통한 노드 재정렬은 한쪽에서만 발생하므로 O(logN)의 시간이 걸린다.

삭제는 최대 or 최소 값을 찾아서 제거하는 경우 이므로, 

루트 노드를 제거하고, 가장 마지막 노드를 루트로 가져온 후,

재정렬 하기 때문에 삽입과 마찬가지로 O(logN)의 시간이 걸린다.

[Code]

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

int main() {
   priority_queue<int, vector<int>, less<int>> maxHeap;
   priority_queue<int, vector<int>, greater<int>> minHeap;

   maxHeap.push(2);
   maxHeap.push(1);
   maxHeap.push(3);

   minHeap.push(2);
   minHeap.push(1);
   minHeap.push(3);

   cout << "max heap top:" << maxHeap.top() << endl;
   cout << "min heap top:" << minHeap.top() << endl;

   return 0;
}

[출처]

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

http://dyngina.tistory.com/24