[Heaps] heap 개념알아보기

출처: leetcode 

 

힙이란 데이터를 저장하는 컨테이너로 Priority queue 로도 불린다. 

다음과같은 오퍼레이션이있다.

• Add an element in O(logn)
• Remove the minimum element in O(log⁡n)
• Find the minimum element in O(1)

Heap sort example (https://commons.wikimedia.org/wiki/File:Heap_sort_example.gif)

 

*힙으로는 최대 요소값을 찾을수있으며 최대값을 찾거나 제거할때는 max heap이라불리면 최소값을 찾거나 제거할때는 min heap이라 불린다.

 

---

Implementation

해쉬맵과 같이 힙도 대부분의 프로그램 언어에서 기본적 라이브러리가 제공되기 때문에 굳이 작동 코드를 알아야할 필요는 없지만 인터페이스를 이해해야한다. 허나 인터뷰에서는 해쉬맵과는다르게 heap의 implementation을 알아야한다.

 

대표적으로 쓰이는 binary heap 은 Array로 구성되어있다.  binary heap은 binary tree로 구성될수있는데 이때 루트 노드는 가장 작은 값을 가지는 특성이있다. 여기서 array로 트리를 구성하는법을 설명하는데 인덱스 0 이 루트 노드이고 인덱스 1,2가 각각 child노드가되며 인덱스 3,4는 인덱스1의 child노드로 2i + 1 and 2i + 2 규칙으로 뻗어나간다고한다.!

 

힙을 사용하면 대부분의 많은 문제들을 time complexity가 O(N^2)에서 O((nlogn)으로 바꿀수있어 매우 속도를 빠르게 할 수 있다. 

 

int main() {
    // Note: C++ priority_queue implements a max heap by default
    
    vector<int> nums = {67, 341, 234, -67, 12, -976};
    priority_queue<int> heap(nums.begin(), nums.end());
    
    heap.push(7451);
    heap.push(-5352);
    
    // The numbers will be printed in sorted order
    while (!heap.empty()) {
        cout << heap.top() << endl;
        heap.pop();
    }
}

이걸 돌리면 가장 큰값부터 출력되는 sort가 되서 나온다.  다음 챕터는 더 다양한 예제를 다뤄본다

7451
341
234
67
12
-67
-976
-5352