최대 힙(Max Heap)과 우선순위 큐의 원리와 구현 - soo:bak

작성일 :

개요

최대 힙(Max Heap)은 우선순위가 가장 높은 요소를 빠르게 꺼낼 수 있도록 설계된 자료구조입니다.

이 구조는 완전 이진 트리를 기반으로 하며, 부모 노드는 항상 자식 노드보다 크거나 같은 값을 가지는 특성을 가집니다.

이를 통해 항상 루트에 가장 큰 값이 위치하게 되어, 최대값을 \(O(1)\) 시간에 조회할 수 있습니다.

이러한 최대 힙 구조는 우선순위 큐(priority queue)를 효율적으로 구현하는 핵심 기반이 됩니다.


우선순위 큐란?

우선순위 큐는 삽입되는 순서와 관계없이 우선순위가 높은 데이터를 먼저 꺼낼 수 있는 큐입니다.

  • 일반적인 큐(FIFO)와는 다르게, 우선순위 개념이 내포되어 있음
  • 가장 큰 값 또는 가장 작은 값을 빠르게 꺼낼 수 있어야 함

이를 위해 배열이나 리스트를 단순히 정렬하며 구현할 수도 있지만,

최대 힙이나 최소 힙을 사용하면 삽입과 삭제 모두를 효율적으로 처리할 수 있습니다.


최대 힙의 성질

  • 완전 이진 트리 구조: 트리가 위에서 아래로, 왼쪽에서 오른쪽으로 차례대로 채워집니다.
  • 힙 성질(heap property): 각 부모 노드는 자식 노드보다 크거나 같은 값을 가집니다.

즉, 다음과 같은 구조를 가집니다:

1
2
3
4
5

       50
      /  \
    30    40
   / \    /
 10  20  35
  • 루트 노드(50)는 항상 가장 큰 값입니다.
  • 삽입과 삭제 후에도 이 성질을 유지하도록 heapify(재정렬) 과정을 수행합니다.

heapify란?

heapify는 힙 구조의 성질이 무너졌을 때, 이를 다시 복원하는 과정입니다.

이 과정은 다음 두 가지 상황에 따라 나뉩니다:

  • 상향 heapify (up-heap)
    • 새로운 값을 힙에 삽입한 후, 해당 노드를 부모 노드와 비교하면서 위로 올라가며 위치를 바꿉니다.
    • 삽입 연산 시 사용됩니다.
  • 하향 heapify (down-heap)
    • 루트 노드를 삭제하고 마지막 노드를 루트에 올린 후, 자식 노드와 비교하여 더 큰 자식과 위치를 바꿔가며 아래로 내려갑니다.
    • 삭제 연산 시 사용됩니다.

이러한 재정렬 과정은 힙의 높이에 비례하므로 시간 복잡도는 \(O(\log n)\)입니다.

힙 구조는 이 과정을 통해 항상 정해진 순서 구조를 유지하게 됩니다.


주요 연산과 시간 복잡도

연산 설명 시간 복잡도
삽입 (Insert) 새로운 값을 힙에 추가하고 재정렬 \(O(\log n)\)
삭제 (Pop) 최대값을 제거하고 힙을 재정렬 \(O(\log n)\)
조회 (Top) 현재 힙에서 가장 큰 값 조회 \(O(1)\)

삽입과 삭제 모두 트리의 높이에 비례하여 연산이 수행되므로, 로그 시간 복잡도를 가집니다.


삽입 연산의 흐름

  1. 새로운 값을 힙의 마지막 자리에 삽입
  2. 부모 노드와 값을 비교하여 위로 올려보냄 (up-heap)
  3. 힙 성질이 유지될 때까지 반복

예시:

  • 기존 힙:
1
2
3
4
5

       50
      /  \
    30    40
   / \    /
 10  20  35

  • 새로운 값 60 삽입

  • 우선 완전 이진 트리 속성에 따라 다음 위치에 삽입:

1
2
3
4
5

       50
      /  \
    30    40
   / \    / \
 10  20  35  60
  • 60이 부모 40보다 크므로 위치를 바꿈:
1
2
3
4
5

       50
      /  \
    30    60
   / \    / \
 10  20  35  40
  • 계속해서 60이 부모 50보다 크므로 루트와 위치를 바꿈:
1
2
3
4
5

       60
      /  \
    30    50
   / \    / \
 10  20  35  40
  • 루트에 도달했으므로 상향 heapify 완료


삭제 연산의 흐름 (최댓값 제거)

  1. 루트 노드를 제거하고, 마지막 노드를 루트에 배치
  2. 자식 노드와 비교하면서 더 큰 자식과 위치를 교환 (down-heap)
  3. 힙 성질이 유지될 때까지 반복

예시:

  • 기존 힙:
1
2
3
4
5

       60
      /  \
    30    50
   / \    / \
 10  20  35  40
  • 루트 제거 후 40을 루트로 이동:
1
2
3
4
5

       40
      /  \
    30    50
   / \    /
 10  20  35
  • 40이 자식 노드 중 더 큰 값인 50보다 작으므로 교환:
1
2
3
4
5

       50
      /  \
    30    40
   / \    /
 10  20  35
  • 교환 후 힙 성질이 유지되므로 하향 heapify 완료


C++ 우선순위 큐 예시

C++의 STL에서 최대 힙은 다음과 같이 priority_queue 클래스를 사용하여 구현되어 있습니다:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include <bits/stdc++.h>
using namespace std;

int main() {
  priority_queue<int> pq;

  pq.push(40);
  pq.push(10);
  pq.push(50);
  pq.push(20);

  cout << pq.top() << "\n"; // 50
  pq.pop();
  cout << pq.top() << "\n"; // 40

  return 0;
}
  • push: 값 삽입
  • pop: 최댓값 제거
  • top: 최댓값 확인

내부적으로 make_heap, push_heap, pop_heap 등의 로직을 활용하여 힙 성질을 유지합니다.


응용 예시

  • 자료 스트리밍 처리: 최대값/최솟값을 실시간으로 유지해야 할 때
  • 스케줄링 문제: 가장 우선순위가 높은 작업 먼저 처리
  • 다익스트라 알고리듬: 최단거리 우선 탐색 시 사용
  • K번째 큰 수 찾기: 정렬 없이 중간 값 추출 가능
    • 많은 알고리듬 문제에서 “전체 수열 중 K번째로 큰 수를 구하라”는 요구가 자주 등장합니다 :
      일반적인 방법은 배열을 정렬한 뒤 K번째 요소를 찾는 방식이지만,
      이 경우 정렬의 시간 복잡도는 \(O(n \log n)\)으로 다소 비효율적일 수 있습니다.

      이때 최대 힙 또는 최소 힙을 활용하면 불필요한 전체 정렬 없이 필요한 값만 빠르게 추출할 수 있습니다.


K번째 큰 수 찾기 - 최대 힙을 이용한 방법 (상위 K개 유지)

  1. 입력값을 순차적으로 최대 힙에 삽입합니다.
  2. 힙의 크기가 K를 초과하면, 가장 큰 값을 하나 제거합니다.
  3. 마지막에 남은 힙의 루트가 K번째로 큰 수가 됩니다.

하지만, K번째 큰 수 찾기는 보통 최소 힙을 사용해 상위 K개의 수를 유지하는 형태로 더 자주 사용됩니다:

  • 이는 효율성 측면에서 유리하기 때문입니다.

    최소 힙을 사용하면 K개의 가장 큰 원소들만 힙에 유지하고,

    그 중 가장 작은 값(즉, K번째로 큰 값)에 즉시 접근할 수 있습니다.

    또한 새로운 값이 들어올 때마다 현재 K번째 값과 한 번의 비교만으로 불필요한 값을 빠르게 제거할 수 있어,

    메모리 사용량과 연산 횟수를 최적화할 수 있습니다.

    원리는 최대힙을 이용하는 경우와 유사합니다.

C++ 코드 예시 (최대 힙 사용)

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include <bits/stdc++.h>
using namespace std;

int findKthLargest(const vector<int>& nums, int k) {
  priority_queue<int> maxHeap;

  for (int num : nums)
    maxHeap.push(num);

  for (int i = 1; i < k; ++i)
    maxHeap.pop();

  return maxHeap.top();
}


K번째 큰 수 찾기 - 최소 힙을 이용한 방법 (K개 유지, 가장 작은 것이 K번째 큰 수)

  1. 수를 읽으며 힙의 크기가K보다 작으면 무조건 삽입합니다.
  2. 힙의 크기가 K가 되면, 이후 들어오는 수와 비교해 더 큰 수만 힙에 넣고 가장 작은 수는 제거합니다.
  3. 최종적으로 루트에 남아 있는 수가 K번째로 큰 값입니다.

이 방식은 전체 정렬 없이 \(O(n \log K)\) 시간 복잡도로 해결할 수 있으며,

특히 데이터가 많거나 스트리밍 입력인 경우 효율적입니다.

C++ 코드 예시 (최소 힙 사용)

1
2
3
4
5
6
7
8
9
10
11
12
13

#include <bits/stdc++.h>
using namespace std;

int findKthLargest(vector<int>& nums, int k) {
  priority_queue<int, vector<int>, greater<int>> minHeap;

  for (int num : nums) {
    minHeap.push(num);
    if (minHeap.size() > k) minHeap.pop();
  }

  return minHeap.top();
}


마무리

최대 힙은 가장 큰 값을 빠르게 조회하고, 효율적으로 삽입/삭제할 수 있는 자료구조입니다.

특히 우선순위 큐와 결합되면 다양한 탐색 및 스케줄링 문제 해결에 효율적인 도구로 사용할 수 있습니다.

관련 문제: [백준 1927] 최소 힙 (C#, C++) - soo:bak

관련 문제: [백준 11279] 최대 힙 (C#, C++) - soo:bak

이 블로그의 다른 글