[알고리즘 / C++] 최소 힙, 최대 힙, 우선순위 큐 (min heap, max heap, priority queue)

알고리즘 문제를 풀다보니 priority queue를 사용하는 문제가 많이 나와서 확실히 개념을 정립하고 가야겠다는 생각이 들었다.

힙(Heap) 이란?

힙은 트리기반의 자료구조로 완전이진트리의 형태로 되어 있다.

최대값이나 최소값을 빠르게 찾아낼 수 있고 재배열이 바로바로 이루어져서 굉장히 편리하다.

완전이진트리 (Complete Binary Tree)

트리란 본래 parent 노드를 기준으로 자식 노드들이 연결되어 있는 구조를 말하는데, 이진트리는 각 부모 노드가 최대 2개의 자식 노드만 가질 수 있다.

그 중에서도 완전이진트리는 한 레벨씩 차곡차곡 쌓아나가야 하는 동시에 모든 자식 노드들은 왼쪽에서부터 차례로 노드들이 채워져야 한다.

위와 같은 트리는 두번째 레벨이 채워져 있지 않은데 세번째 레벨이 채워져 있으므로 완전이진트리가 아니다.

두번째 레벨이 다 채워져 있지만 마지막 레벨의 노드들이 왼쪽부터 차례대로 채워져 있지 않기 때문에 완전이진트리가 아니다.

이러한 완전이진트리를 힙에서 사용하는 이유는 배열로 구현할 수 있기 때문인데, 노드가 들어가는 순서가 정해져 있기 때문에 몇번째 위치에 어떤노드가 들어가 있는지 파악할 수 있게 된다.

최대 힙, 최소 힙 Max heap, Min heap

그렇다면 최대 힙과 최소 힙은 어떻게 다른것일까?

처음에는 두개가 뭐가 다른지 좀 헷갈렸는데 루트에 어떤 노드가 위치하는지만 생각하면 쉽게 구별이 가능하다.

최대 힙은 루트에 최댓값을 가지는 힙이다! 그래서 자식 노드는 항상 부모노드보다 작을 수 밖에 없다.

부모 노드의 값 >= 자식 노드의 값

최소 힙은 루트에 최소값을 가지는 힙으로 자식 노드는 항상 부모 노드보다 클 수 밖에 없다.

부모 노드의 값 <= 자식 노드의 값

이것은 최대 값이 루트에 있기 때문에 max heap이고

이것은 최소 값이 루트에 있기 때문에 min heap이다.

물론 같은 값이 들어가는 것도 가능하다.

이것을 배열로 구현한다고 하면

부모 노드의 인덱스가 i일때 왼쪽 자식의 인덱스는 2 * i + 1, 오른쪽 자식의 인덱스는 2 * i + 2가 되는 것을 볼 수 있다.

예를들어 2를 예로 들면 인덱스는 1이고 왼쪽 자식인 4의 인덱스는 2 * 1 + 1 = 3, 오른쪽 자식인 5의 인덱스는 2*1 + 2 = 4 가 되게 된다.

우선순위 큐 priority queue

저런 힙을 직접구현해도 되지만 우리 C++에는 라이브러리들이 있다. 코테 볼때 하나하나 구현하고 있을 시간은 없으니 미리 구현되어 있는 것을 이용하도록 하자

여기서는 바로 prioirty queue를 이용하는 것이다.

사실 우선순위 큐는 우선순위가 제일 높은 것부터 순서대로 빼는 자료구조라 heap으로 구현해야 할 필요는 없다. 하지만 우선순위 별로 뺀 다는 점이 heap과 동일하고 시간복잡도도 굉장히 좋기 때문에 heap을 사용해서 구현하게 된다.

즉 우선순위 큐 != heap 이지만 우선순위 큐를 Heap으로 구현한다고 생각하면 된다~

C++ 우선순위 큐 사용하기

#include <queue>

안에 priority_queue 가 들어있으므로 위의 코드를 선언해준 후 사용하면 된다.

#include <iostream>
#include <queue>

int main() {
    // Max Heap 기반 우선순위 큐
    std::priority_queue<int> maxHeap;

    // Min Heap 기반 우선순위 큐
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

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

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

    while (!maxHeap.empty()) {
        std::cout << maxHeap.top() << " ";
        maxHeap.pop();
    }

    while (!minHeap.empty()) {
        std::cout << minHeap.top() << " ";
        minHeap.pop();
    }

    return 0;
}

위와 같은 간단한 예제를 이용해서 살펴보게 되면

기본적으로 C++에서 우선순위큐는 maxHeap으로 설정되어 있다. 즉 Root에 가장 큰 원소가 들어가 있다는 뜻이다. 그러므로 maxHeap을 선언해줄 때는 단순히

std::priority_queue<int> maxHeap;

로 선언해서 사용하면 된다.

하지만 minHeap을 사용하고 싶다면

std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

위와 같이 비교 함수 greater를 추가해줌으로써 root에 최소가 오고 점점 커지도록 선언해줄 수 있다.

반대로 maxHeap에서는 기본적으로 less 비교함수를 사용한다고 생각하면 된다.

일반 queue를 사용하는 것처럼 push, pop 함수로 진행하면 되며

minHeap과 maxHeap은 각각 위의 그림같은 모양이 될 것이다.

우선순위 큐 시간복잡도, 공간복잡도

우선순위 큐 사용방법을 익혔으니 이제 궁금해진 점은 시간복잡도와 공간복잡도이다.

본래 힙에서 삽입, 삭제 연산은 O(logN)의 성능을 가지는 매우 빠른 자료구조이다.

배열이나 linked list를 사용하면 최악의 경우 매우 느린 시간복잡도를 가질 수도 있지만 힙은 효율적이다.

마찬가지로 MinHeap, MaxHeap에서도 삽입, 삭제 연산은 O(logN)이다.

또한 pop은 무려 O(1)을 가지게 되는데 단순히 root에 있는 노드를 빼오면 자동으로 재배열 되기 때문이다. 이것이 라이브러리로 구현되어 있기 때문에 우리같은 입장에서는 너무 편하게 제일 큰 값 / 제일 작은 값을 가져올 수 있다.

복잡하게 linked list가 없이도 힙은 아까 봤던 것처럼 배열로 구할 수 있기 때문에 공간복잡도도 효율적이라고 할 수 있다.

우선순위 큐 장점, 단점

장점

1. 원소 관리 굉장히 효율적
2. 자동 재배열
3. pair를 이용한다면 여러 문제에서 사용가능

단점

1. 중간 원소에는 접근이 불가하다
2. 우선순위 바꾸려면 힘들다

다익스트라 알고리즘, 프림 알고리즘, 스케쥴링 등등등 너무 많은 곳에서 우선순위 큐를 사용하게 되고 c++의 pair와 함께하게 된다면 경우의 수를 구하는 문제나 횟수를 판단하는 문제에서 기본적으로 minHeap, maxHeap중 하나를 사용한다고 깔아 놓는 방법도 괜찮을 듯 하다.

시간복잡도도 괜찮아서 문제를 좀더 어렵게 풀수는 있어도 시간복잡도에 걸릴일은 없을듯하다.