[DS] 10. 우선순위 큐/힙

우선순위 큐(Priority Queue)?

std::priority_queue<int> pq;
std::priority_queue<int, std::vector<int>, std::greater<int>> pq_greater;
std::priority_queue<int, std::vector<int>, std::less<int>> pq_less;

데이터들이 우선순위를 가지고 있으며, 우선순위가 높은 데이터가 먼저 출력되는 자료구조.

일반적인 큐에서는 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO) 방식으로 동작한다.

반면 우선순위 큐에서는 데이터들이 우선순위를 가지고 있어, 우선순위가 높은 데이터가 먼저 출력된다.

---

추상 자료형

데이터 : 우선순위를 가진 자료들의 모음.

연산 :

함수	설명
insert(x)	데이터 x를 우선순위 큐에 삽입한다.
remove()	우선순위가 가장 높은 요소를 삭제 및 반환한다.
find()	우선순위가 가장 높은 요소를 삭제하지 않고 반환한다.
isEmpty()	우선순위 큐가 비어있는지 여부를 반환한다.
isFull()	우선순위 큐가 포화 상태인지를 반환한다.
display()	우선순위 큐의 모든 요소를 출력한다.

---

사용법 (std::priority_queue)

표준 라이브러리의 Priority Queue는 힙 기반으로 구현되어있다. 이는 아래에서 설명한다.

메서드

함수	설명
push(x)	데이터 x를 우선순위 큐에 삽입한다.
emplace(args...)	인자 args...를 이용해 요소를 우선순위 큐 내부에서 직접 생성한다.
pop()	우선순위가 가장 높은 요소를 삭제한다. 반환 타입은 void이다.
top()	우선순위가 가장 높은 요소를 삭제하지 않고 반환한다.
empty()	우선순위 큐가 비어 있다면 true, 아니라면 false를 반환한다.
size()	우선순위 큐에 저장된 요소의 개수를 반환한다.
swap(pq)	다른 우선순위 큐 pq와 내부 요소 및 비교 객체를 서로 교환한다.
push_range(rg)	범위 rg에 포함된 요소들을 우선순위 큐에 삽입한다. (C++23 이상)

---

우선순위 큐의 구현 방법

우선순위 큐는 배열/연결 리스트/힙 등을 이용하여 구현할 수 있다.

다만 배열과 연결 리스트를 통한 구현은 이게 가능하다 정도이지, 삽입이나 삭제 둘 중 하나에서 큰 비효율이 발생하기에 실제로 사용하기에는 무리가 있다.

힙으로 구현하는 방향이 삽입/삭제 양쪽에서 균형있는 효율을 보여주기에 일반적으로 선호되며, 실제로 현대 자료구조에서의 우선순위 큐는 대부분 힙(Heap)을 기반으로 구현되어있다.

배열을 사용하는 방법

정렬되지 않은 배열

삽입	그냥 맨 뒤에 추가하면 되므로 $O(1)$
삭제	전체를 순회하며 우선순위가 가장 높은 값을 찾아야 하므로 $O(n)$

삭제 시에는 반드시 처음부터 끝까지 모든 요소들을 스캔하면서 가장 우선순위가 높은 값을 찾아야 한다. 때문에 그만큼의 비용이 발생한다.

여기에 더해, 삭제 후 빈 자리를 메우기 위해 뒤의 값을 모두 당겨오는 부담도 있다.

정렬된 배열

삽입	삽입 지점의 탐색에 더해, 기존 요소들을 뒤로 밀어내야 하므로 $O(n)$
삭제	우선순위가 높은 요소가 항상 맨 뒤에 있으므로 $O(1)$

정렬된 상태를 항상 유지해야 하기에 삽입 시 정렬이 일어나며, 이에 따라 값을 밀어야 하기에 그만큼의 비용이 발생한다.

연결 리스트를 사용하는 방법

정렬되지 않은 연결 리스트

삽입	그냥 맨 앞에 추가하면 되므로 $O(1)$
삭제	전체를 순회하며 우선순위가 가장 높은 값을 찾아야 하므로 $O(n)$

정렬되지 않은 배열과 크게 다르지 않다. 차이가 있다면 삭제 시 빈 자리를 채우기 위한 shift 연산이 없어서 조금이나마 비용이 적다는 것.

정렬된 연결 리스트

삽입	전체를 순회하며 삽입 할 위치를 찾아야 하므로 $O(n)$
삭제	그냥 첫 번째 노드를 삭제하면 되므로 $O(1)$

이 역시 정렬된 배열과 크게 다르지 않다. 차이 또한 삽입 시 자리를 내기 위해 옆으로 미는 shift 연산이 없어서 조금이나마 비용이 적다는 것.

힙을 사용하는 방법

힙(Heap)은 우선순위 큐를 위해 제작된 자료구조이다.

이를 사용하면 삽입과 삭제를 모두 $O(\log_2(n))$에 처리할 수 있다. 이에 대해 자세한 내용은 후술.

요약

구현 방법	삽입	삭제
정렬되지 않은 배열 / 연결 리스트	$O(1)$	$O(n)$
정렬된 배열 / 연결 리스트	$O(n)$	$O(1)$
힙	$O(\log_2(n))$	$O(\log_2(n))$

예시로, 데이터가 1천개라고 가정할 시 최악의 연산량은 다음과 같다.

구현 방법	삽입	삭제
정렬되지 않은 배열 / 연결 리스트	$1$	$1000$
정렬된 배열 / 연결 리스트	$1000$	$1$
힙	$3$	$3$

---

힙(Heap)?

여러 값 중 최댓값이나 최솟값을 빠르게 찾을 수 있도록 만든 완전 이진트리 기반의 자료구조.

사전 정의 상 힙은 더미라고 하는데, 이와 유사하게 더미 모양으로 데이터가 쌓여있는 듯한 구조를 띈다.

힙은 부모 노드와 자식 노드 사이의 대소 관계에 따라 아래와 같이 두 종류로 나뉜다.

• 최대 힙(Max Heap) : 부모 노드의 값이 자식 노드의 값보다 크거나 같다.
• 최소 힙(Min Heap) : 부모 노드의 값이 자식 노드의 값보다 작거나 같다.

힙은 완전 이진트리의 형태를 가지며, 전체 데이터가 완전히 정렬되어 있지는 않지만 부모와 자식 사이의 우선순위 관계는 유지된다. 즉, 부모의 값은 자식보다 항상 우선순위가 높다.

아래 설명에서는 최대 힙을 기준으로 설명한다.

배열로 표현하는 힙

완전 이진트리는 배열을 이용하면, 아래와 같은 규칙을 통해 효율적으로 표현할 수 있다.

대상	인덱스 (시작 index를 1로 가정)
왼쪽 자식	parent * 2
오른쪽 자식	parent * 2 + 1
부모	child / 2

완전 이진트리이기 때문에 노드 사이에 빈 공간이 존재하지 않는다. 이를 통해 각 노드의 위치를 인덱스 계산만으로 구할 수 있으며, 덕분에 탐색이 $O(\log_2(n))$으로 빠르다.

힙의 구현

코드 예제

#include <array>
#include <iomanip>
#include <iostream>

class HeapNode
{ // 노드
  int key;

public:
  HeapNode(int k = 0): key(k) {}

  void setKey(int k)    key = k;
  int getKey()          return key;
  void display()        std::cout << std::setw(4) << key;
};

class MaxHeap
{ // 최대 힙
  static constexpr int MAX_ELEMENT = 200;

  std::array<HeapNode, MAX_ELEMENT> node;
  int size;

public:
  MaxHeap() : size(0) {}
  
  bool isEmpty()              return size == 0;
  bool isFull()               return size == MAX_ELEMENT - 1;

  HeapNode& getParent(int i)  return node[i / 2];
  HeapNode& getLeft(int i)    return node[i * 2];
  HeapNode& getRight(int i)   return node[i * 2 + 1];

  void insert(int key)        { /* ... */ }; // 아래 삽입 연산 참조
  HeapNode remove()           { /* ... */ }; // 아래 삭제 연산 참조
  HeapNode find() const       return node[1];

  void display() const
  {
    for (int i = 1, level = 1; i <= size; ++i)
    {
      if (i == level)
      {
        if (i != 1)
          std::cout << std::endl;
        level *= 2;
      }
      node[i].display();
    }
    std::cout << std::endl << "--------------------------------";
  }
};

---

힙의 삽입 연산

힙에 새로운 데이터를 삽입할 때는 먼저 완전 이진트리의 마지막 위치에 데이터를 추가한다.

그 뒤 부모 노드와의 값을 비교하면서, 힙의 조건을 만족할 때까지 위로 이동시킨다.

삽입 연산 진행 순서

1. 가장 마지막 위치에 새로운 데이터를 삽입한다.
2. 부모 노드와 값을 비교하여, 자식이 더 크다면 교환한다.
3. 2번을 힙의 조건을 만족할 때 까지 반복한다.

비유로 들자면, 신입사원을 일단 말단 자리에 배치한 뒤, 능력에 따라 승진시키는 과정과 유사하다.

코드 예제

void insert(int key)
{
  if (isFull())
    return; // 힙이 가득 찬 경우

  int i = ++size; // 새로운 마지막 위치에서 시작

  // 부모 노드와 비교하며 위로 이동하는 과정
  while (i != 1 && key > getParent(i).getKey())
  {
    node[i] = getParent(i); // 부모 노드를 한 단계 아래로 이동
    i /= 2;                 // 부모 노드의 위치로 이동
  }

  node[i].setKey(key); // 최종 위치에 데이터 저장
}

---

힙의 삭제 연산

먼저 루트 노드를 삭제한 뒤, 트리의 마지막 노드를 루트 자리로 옮긴다.

그 뒤 자식 노드와 값을 비교하며 힙의 조건을 만족할 때까지 아래로 이동시킨다.

삭제 연산 진행 순서

1. 우선 루트 노드를 삭제하고, 그 자리에 마지막 노드를 옮겨온다.
2. 두 자식 노드 중 더 큰 값을 가진 노드와 교환한다.
3. 2번을 힙의 조건을 만족할 때 까지 반복한다.

비유로 들자면, 우선 사장을 제거한 뒤 말단에 있던 신입사원을 공석에 배치하고, 능력에 맞게 강등시키는 과정과 유사하다.

코드 예제

HeapNode MaxHeap::remove()
{
  if (isEmpty())
    return HeapNode();

  HeapNode item = node[1];      // 루트 노드 저장
  HeapNode last = node[size--]; // 마지막 노드 저장, 이후 힙 크기 감소

  int parent = 1;               // 루트 위치에서 시작
  int child = 2;                // 루트의 왼쪽 자식 위치

  while (child <= size)
  { // 두 자식 노드 중 더 큰 자식 노드를 선택
    if (child < size && 
        getLeft(parent).getKey() < getRight(parent).getKey())
      ++child;

    // 마지막 노드가 자식보다 크거나 같다면 이동을 종료
    if (last.getKey() >= node[child].getKey())
      break;
    // 그렇지 않다면, 자식 노드를 한 단계 위로 이동
    node[parent] = node[child]; 
    parent = child;             // 현재 위치를 자식 위치로 이동
    child *= 2;                 // 다음 자식 위치로 이동
  }
  node[parent] = last;          // 마지막 노드를 최종 위치에 저장
  return item;                  // 삭제한 루트 노드 반환
}

---

힙의 복잡도

완전 이진 트리의 높이는 $\log_2(n)$이며, 힙의 삽입/삭제 연산은 트리의 높이에 비례하게 비교/교환을 진행한다.

때문에 힙의 삽입/삭제의 시간 복잡도는 $O(\log_2(n))$이다.

---

힙의 응용

힙 정렬

힙에 데이터들을 삽입한 뒤, 루트 노드를 반복해서 삭제하면 우선순위에 따라 정렬된 결과를 얻을 수 있으며, 이러한 정렬 방법을 힙 정렬(Heap Sort)이라고 한다.

삽입과 삭제를 이어서 진행하므로, 힙 정렬의 시간 복잡도는 삽입 + 삭제인 $n \log_2(n) + n \log_2(n)$ 에 비례한다. 그러므로 $O(n \log_2(n))$이 된다.

STL의 우선순위 큐를 이용한 정렬

C++ STL에서는 <queue> 헤더를 통해 우선순위 큐를 제공한다.

#include <iostream>
#include <queue>

int main()
{
  std::priority_queue<int> pq;

  pq.push(30);
  pq.push(10);
  pq.push(20);

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

  return 0;
}

30 20 10

std::priority_queue는 기본적으로 큰 값이 먼저 출력되는 최대 힙으로 동작한다.

작은 값이 먼저 출력되도록 하려면 <functional> 헤더의 std::greater를 사용할 수 있다.

// 상기 코드에서 pq 선언 부분만 아래로 변경.
std::priority_queue<int, std::vector<int>, std::greater<int>> pq;

10 20 30

허프만 코드

허프만 코드(Huffman Code)는 문자의 출현 빈도에 따라 서로 다른 길이의 비트 코드를 할당하는 압축 방법이다.

예시로 알파벳에서는 e가 z에 비해 월등히 많이 사용되는데, 여기서 e에는 짧은 코드를 할당하고, z에는 긴 코드를 할당하는 것이다. 이를 통해 데이터 표현에 필요한 저장 공간을 줄일 수 있다.

생성 방법

s : 4, i : 6, n : 8, t : 12, e : 15

위와 같이 각 문자의 빈도수가 주어졌다고 가정하고, 아래의 진행 순서대로 생성을 진행한다.

1. 각 문자별로 노드를 생성한다. 이 때 노드의 값은 사용 빈도수가 된다.
2. 부모가 없는 노드 중, 빈도수가 가장 작은 두 노드를 선택한다.
3. 두 노드를 자식으로 가지는 새로운 부모 노드를 생성한다.
4. 부모 노드의 빈도수는 두 자식 노드의 빈도수 합으로 설정한다.
5. 부모가 없는 노드들을 대상으로 위 과정(2~4)을 반복한다.
6. 하나의 트리만 남으면 부모로부터 자식으로 내려가는 왼쪽 간선은 0을, 오른쪽 간선은 1을 할당한다.
7. 루트에서 각 문자까지 이동하며 만나는 비트를 이어 붙여 최종 코드를 만든다.

허프만 코드는 항상 특정 문자의 코드가 다른 문자의 코드 앞부분과 겹치지 않도록 만들어지며, 이 덕분에 코드를 앞에서부터 순서대로 읽어도 어느 문자에 해당하는지 구분할 수 있다.