[알고리즘 개념 정리] Heap, Priority Queue 개념 c++ 구현

Heap이란

힙(Heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(Complete binary tree)를 기본으로 한 자료구조(tree-based structure)다. 최악의 경우가 생겨도 힙은 완전 이진 트리이므로 항상 O(logN)의 시간에 해결될 수 있도록 해준다.

힙을 이용한다면 최댓값 혹은 최솟값을 O(logN)에 찾을 수 있다. (일반 배열 사용시 O(N))

 

최대 힙(Max Heap) / 최소 힙(Min Heap)

최대 힙은 완전 이진트리의 root 부분에 최댓값이 항상 존재하게 되고 최소 힙은 완전 이진트리의 root 부분에 최솟값이 항상 존재하게 된다.

• 최대 힙의 특성: 임의의 subtree에서 root 가 되는 노드를 잡으면 항상 subtree에서의 root 노드는 그 subtree에서 최댓값을 유지한다.
• 최소 힙의 특성 : 임의의 subtree에서 root가 되는 노드를 잡으면 항상 subtree에서의 root 노드는 그 subtree에서 최솟값을 유지한다.
• 주의해야 할 점 : '힙의 자식 노드에서 작은 것이 왼쪽, 큰 것이 오른쪽' 이런 것은 존재하지 않는다. ⇒ 즉, 왼쪽 오른쪽에 무슨 노드가 오던간에 해당하는 subtree에서 루트노드보다 큰 (minheap에서는 작은) 값이면 된다.

실제 구현시, 최소 힙은 최대 힙에서 읍수 값으로만 구현해주면 되기 때문에 최대 힙 구현만 알고 있으면 됨.

최대 힙 삽입 과정(push)

1. Insert 할 값을 힙의 마지막 위치에 삽입한다.
2. 부모 노드와 비교를 해서 Insert 할 값이 더 크다면 swap 해준다.
3. 2번 과정을 계속 반복한다.

최대 힙 삭제 과정(pop)

pop 이기 때문에 root 부터 삭제하면 된다고 이해하면 될듯.

1. 삭제할 값(root)를 빼낸다.
2. 힙에서 마지막에 있는 노드를 root 로 올린다.
3. root로 올린 노드와 그 자식들의 노드를 비교해서 swap 해준다.
4. 2~3번 과정을 반복한다.

이진 탐색 트리(Binary Search Tree) 와의 차이점

• 힙은 자식 노드가 부모 노드보다 크면 오른쪽으로 삽입, 작으면 왼쪽으로 삽입 과 같은 조건이 존재하지 않는다.
• 하지만 이진 탐색 트리에서의 노드별 값 크기순은 왼쪽 자식 < 부모 < 오른쪽 자식 순으로 된다.

 

---

코드 구현

#include <iostream>
#include <cstdio>

using namespace std;

template <typename T>
class HEAP {
private:
    int _sz;
    T *heapArr;

    int max(int a, int b) {
            return a>b;
    }

    /*
    * k번째 노드의 자식이 k*2, K*2+1
    * 부모는 k
    * 부모는 /2 로 확인이 가능하며 (k*2)/2 그리고 (k*2+1)/2 로 나타낼 수 있다.
    */
    void push_swap(int cur) {
            if(cur == 1)
                return;

            int par = cur / 2;
            if(heapArr[par] < heapArr[cur]) {
                    T tmp = heapArr[par];
                    heapArr[par] = heapArr[cur];
                    heapArr[cur] = tmp;
                    push_swap(cur / 2);
            }
    }

    /*
    * 왼쪽 자식이 존재한다면 cur*2 가 힙의 크기보다 작거나 같아야 한다 == 자식 존재 여부 판단
    * left와 right를 위와 같은 방식으로 구하고 자식이 없다면 -1 이라는 값으로 set
    * 힙이 완전 이진 트리 기반이기 때문에 왼쪽 자식이 없으면 당연히 오른쪽 자식은 없다.
    */
    void pop_swap(int cur) {
            int left, right, child;
            left = (cur * 2 <= _sz ? cur * 2 : -1);
            right = (cur * 2 + 1 <= _sz ? cur % 2 + 1: -1);

            if(left == -1 && right == -1) 
                    child = -1;
            else if(left != -1 && right == -1)
                    child = left;
            else
                    child = (heapArr[left] > heapArr[right] ? left : right);

            if(child == -1)
                    return;
            // 자신보다 자식이 더 큰 값을 가젔을 때 swap
            if(heapArr[child] > heapArr[cur]) {
                    T tmp = heapArr[child];
                    heapArr[child] = heapArr[cur];
                    heapArr[cur] = tmp;
                    pop_swap(child);
            }
    }

public:
    HEAP(int n) {
        int _sz = 0;
        heapArr = new int[n + 1];
    }
    ~HEAP() {
        delete[] heapArr;
    }

    int empty() {
        return !_sz;
    }

    int size() {
        return _sz;
    }

    T top() {
        return !_sz ? -1 : heapArr[1];
    }

    /*
    * Heap의 마지막 부분에 삽입 (_sz = 힙의 크기)
    */
    void push(int val) {
        heapArr[++_sz] = val;
        push_swap(_sz);
    }

    /*
    * !_sz == 0 이면 pop 할것이 없으니 return
    * 힙의 root를 우선 삭제해주고 힙의 마지막에 위치한 값을 root에 넣어준다 == heapArr[1] = heapArr[_sz--];
    */
    void pop() {
        if (!_sz)
            return;

        heapArr[1] = heapArr[_sz--];
        pop_swap(1);
    }
};

int main() {
    int size;
    cin >> size;
    HEAP<int> pq(size);

    int arr[] = {2, 4, 11, 12, 8, 10, 14, 12, 20};
    for(int i = 0; i < sizeof(arr) / sizeof(int); i++) 
        pq.push(arr[i]);

    pq.push(30);
    pq.push(15);

    pq.pop();
    pq.pop();

    cout << "최종적으로 maxheap에서의 root 값 : " << pq.top() << endl;
    return 0;
}

 

STL 활용 (priority_queue)

• 힙 기반 데이터 삽입 시간 복잡도는 O(logn)

• 힙 기반 데이터 삭제 시간 복잡도는 O(logn)

• 정의 방법은 priority_queue<자료형, 구현체, 비교연산자>

  • 자료형은 int, double, 선언한 클래스 등등
  • 구현체는 기본적으로 vector<자료형> 으로 정의된다. 또한, dequeue<자료형> 등을 넣어도 된다.
  • 비교 연산자는 기본적으로 less<자료형> 으로 정의된다. less는 내림차순(큰놈부터나오는)이다. greater<자료형> 을 넣으면 작은놈부터 나온다.

• 예시

  #include <iostream>
  #include <queue>
  #include <vector>
  #include <cstdio>
  
  using namespace std;
  
  struct a {
      int start;
      int end;
      int value;
  };
  
  struct comp{
      bool operator()(a t, a u){
          return t.value < u.value;
      }
  };
  
  int main() {
      priority_queue<a, vector<a>, comp> pq;
      return 0;
  }

---

Reference

• Heap 개념 및 구현 코드 : https://www.crocus.co.kr/1184
• Priority Queue 개념 및 코드 : https://koosaga.com/9