Data Structure (9) Priority Queue

1 우선순위 큐(Priority Queue)

정의: 우선순위 큐 (Priority Queue)

우선순위 큐는 삽입 순서가 아닌 우선순위(priority)에 따라 데이터를 추출하는 자료구조다.

• 일반적으로 힙(Heap) 자료구조로 구현된다
• 삽입: \(O(\log N)\) — 힙 재정렬
• 최솟값/최댓값 추출: \(O(\log N)\) — 힙 재정렬
• Python: heapq 라이브러리 (기본 최소 힙)

• 우선순위 큐는 우선순위에 따라서 데이터를 추출하는 자료구조다.
• 컴퓨터 운영체제, 온라인 게임 매칭 등에서 활용된다.
• 우선순위 큐는 일반적으로 힙(heap)을 이용해 구현한다.

2 왜 필요한가

• 우선순위에 따라 데이터를 처리해야 하는 운영체제 스케줄러, 게임 매칭 시스템에 사용된다.
• 다익스트라(Dijkstra) 최단 경로 알고리즘의 핵심 자료구조다.
• 삽입과 삭제 모두 \(O(\log N)\) 에 처리되어 정렬된 리스트보다 효율적이다.
• 힙(heap) 구조를 활용하여 N번째 최솟값/최댓값을 효율적으로 추출할 수 있다.

표 1: a list of data structure

Number	Data Structure	추출되는 데이터
1	stack	가장 나중에 삽입된 데이터
2	queue	가장 먼저 삽입된 데이터
3	priority queue	가장 우선 순위가 높은 데이터

See 표 2.

3 우선순위 큐를 구현하는 방법

• 우선순위 큐는 다양한 방법으로 구현할 수 있다.
• 데이터의 개수가 N개일 때, 구현 방식에 따른 시간 복잡도는 다음과 같다.
• 삭제 할때는 우선 순위가 가장 높은 것을 찾아야 하기 때문에 \(O(N)\) 만큼 소요될 수 있다.

표 2: a list of the priority queue building methods in Python

Number	우선 순위 큐 구현 방식	삽입 시간	삭제 시간
1	리스트 자료형	\(O(1)\)	\(O(N)\)
2	힙 (Heap)	\(O(logN)\)	\(O(logN)\)

See 표 2.

• 일반적인 형태의 큐는 선형적인 구조를 가진다.
• 반면에 우선순위 큐는 이진 트리(binary tree) 구조를 사용하는 것이 일반적이다.

4 이진 트리(Binary Tree)

• 이진 트리(binary tree)는 최대 2개까지의 자식을 가질 수 있다.

4.1 포화 이진 트리(Full Binary Tree)

• 포화 이진 트리는 리프 노드를 제외한 모든 노드가 두 자식을 가지고 있는 트리다.

4.2 완전 이진 트리(Complete Binary Tree)

• 완전 이진 트리는 모든 노드가 왼쪽 자식부터 차근차근 채워진 트리다.

4.3 높이 균형 트리(Height Balanced Tree)

• 왼쪽 자식 트리와 오른쪽 자식 트리의 높이가 1 이상 차이 나지 않는 트리다.

5 힙(Heap)

• 힙(Heap)은 원소들 중에서 최댓값 혹은 최솟값을 빠르게 찾아내는 자료구조다.
• 최대 힙(Max Heap): 값이 큰 원소부터 추출한다.
• 최소 힙(Min Heap): 값이 작은 원소부터 추출한다.
• 힙은 원소의 삽입과 삭제를 위해 \(O(logN)\) 의 수행 시간을 요구한다.
• 단순한 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일하다.
• 이 경우 시간 복잡도는 \(O(NlogN)\) 이다.

직관적 이해: 응급실 트리아지(triage)와 같다. 먼저 온 순서가 아니라 증상의 긴급도에 따라 먼저 진료한다. 위급한 환자가 도착하면 대기열의 맨 앞으로 올라간다.

최소 힙 구조 (완전 이진 트리):

         1          ← 루트 = 최솟값 (항상 가장 작은 값이 루트)
       /   \
      3     2       ← 부모 ≤ 자식 관계 항상 유지
     / \   / \
    7   4  5   6

삽입(0): 마지막에 추가 후 부모와 비교하며 위로 이동(상향식 heapify)
         → 0이 1보다 작으므로 루트까지 올라감
삭제:    루트(1) 제거 → 마지막 노드(6)를 루트로 이동 → 자식과 비교하며 아래로 이동(하향식 heapify)

5.1 최대 힙(Max Heap)

• 최대 힙(max heap)은 부모 노드가 자식 노드보다 값이 큰 완전 이진 트리를 의미한다.
• 최대 힙(max heap)의 루트 노드는 전체 트리에서 가장 큰 값을 가진다는 특징이 있다.

5.2 힙(Heap)의 특징

• 힙은 완전 이진 트리 자료구조를 따른다.
• 힙에서는 우선순위가 높은 노드가 루트(root)에 위치한다.

1. 최대 힙(max heap)

• 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크다.
• 루트 노드가 가장 크며, 값이 큰 데이터가 우선순위를 가진다.

2. 최소 힙(min heap)

• 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작다.
• 루트 노드가 가장 작으며, 값이 작은 데이터가 우선순위를 가진다.
• 힙의 삽입과 삭제 연산을 수행할 때를 고려해 보자.
• 직관적으로, 거슬러 갈 때마다 처리해야 하는 범위에 포함된 원소의 개수가 절반씩 줄어든다.
• 따라서 삽입과 삭제에 대한 시간 복잡도는 \(O(\log N)\) 이다.

5.3 최소 힙 구성 함수: Heapify

• (상향식) 부모로 거슬러 올라가며, 부모보다 자신이 더 작은 경우에 위치를 교체한다.

5.4 힙에 새로운 원소가 삽입될 때

• (상향식) 부모로 거슬러 올라가며, 부모보다 자신이 더 작은 경우에 위치를 교체한다.
• 새로운 원소가 삽입되었을 때 \(O(\log N)\) 의 시간 복잡도로 힙 성질을 유지하도록 할 수 있다.

5.5 힙에 새로운 원소가 삭제될 때

• 원소가 제거되었을 때 \(O(\log N)\) 의 시간 복잡도로 힙 성질을 유지하도록 할 수 있다.
• 원소를 제거할 때는 가장 마지막 노드가 루트 노드의 위치에 오도록 한다.
• 이후에 루트 노드에서부터 하향식으로(더 작은 자식 노드로) Heapify()를 진행한다.

5.6 파이썬의 힙(Heap) 라이브러리

• 파이썬에서는 힙(Heap) 라이브러리를 제공한다.
• heapq 라이브러리의 삽입 및 삭제에 대한 시간 복잡도는 모두 \(O(\log N)\) 이다.

5.6.1 힙 초기화

• 단순히 하나의 빈 리스트를 만들면, 그것을 힙(heap) 자료구조로 사용할 수 있다.

Python heapq 라이브러리는 최소 힙을 기본으로 제공한다. 빈 리스트를 힙으로 사용하거나, 기존 리스트를 heapify()로 변환한다.

import heapq

heap = []
print(heap)
# 출력: []

5.6.2 삽입(push)과 추출(pop)

• 원소의 삽입: heappush() 메서드
• 원소의 추출: heappop() 메서드

import heapq

heap = []

heapq.heappush(heap, 7)
heapq.heappush(heap, 4)
heapq.heappush(heap, 5)
heapq.heappush(heap, 8)

while heap:
  element = heapq.heappop(heap)
  print(element, end=" ")
# 출력: 4 5 7 8

5.6.3 최솟값 구하기

• 원소의 삽입: heappush() 메서드
• 원소의 추출: heappop() 메서드

import heapq

heap = []

heapq.heappush(heap, 7)
heapq.heappush(heap, 4)
heapq.heappush(heap, 5)
heapq.heappush(heap, 8)

print(heap[0])
# 출력: 4

5.6.4 리스트를 힙으로 변환

• heappush() 메서드를 이용해 하나씩 원소를 삽입하지 않을 수 있다.
• heapify() 메서드는 새로운 리스트를 반환하지 않고, 리스트 내부를 직접 수정한다.

import heapq

heap = [9, 1, 5, 4, 3, 8, 7]
heapq.heapify(heap)

while heap:
  element = heapq.heappop(heap)
  print(element, end=" ")
# 출력: 1 3 4 5 7 8 9

5.6.5 최대 힙(Max Heap)

• 파이썬의 heapq 라이브러리는 기본적으로 최소 힙 기능을 제공한다.
• 최대 힙을 위해서는 1 삽입과 2 추출할 때 키(key)에 음수(-) 부호를 취한다.

heapq는 최소 힙만 제공하므로, 최대 힙이 필요할 때는 값에 음수 부호를 붙여 삽입한다. 꺼낼 때 다시 음수를 취하면 원래 최댓값을 얻는다.

import heapq

arr = [9, 1, 5, 4, 3, 8, 7]
heap = []

for x in arr:
  heapq.heappush(heap, -x)

while heap:
  x = -heapq.heappop(heap)
  print(x, end=" ")
# 출력: 9 8 7 5 4 3 1

5.6.6 활용 예시 1 힙 정렬(Heap Sort)

• 단순히 힙에 원소를 넣었다가 꺼내는 것 만으로도 정렬을 수행할 수 있다.

힙 정렬(Heap Sort)은 모든 원소를 힙에 넣었다가 순서대로 꺼내는 것만으로 정렬을 완성한다. 시간 복잡도는 \(O(N \log N)\)이다.

import heapq

def heap_sort(arr):
  heap = []
  for x in arr:
    heapq.heappush(heap, x)

  result = []
  while heap:
    x = heapq.heappop(heap)
    result.append(x)

  return result

print(heap_sort([9, 1, 5, 4, 3, 8, 7]))
# 출력: [1, 3, 4, 5, 7, 8, 9]

5.6.7 활용 예시 2 N번째로 작은 값

• 최소 힙이나 최대 힙을 사용하여 n번째로 작은 값이나 n번째로 큰 값을 얻을 수 있다.
• 힙(heap)을 만든 뒤에 추출(pop) 함수를 n번 호출한다.

import heapq

def n_smallest(n, arr):
  heap = []
  for x in arr:
    heapq.heappush(heap, x)
    result = None
  for _ in range(n):
    result = heapq.heappop(heap)
  return result

arr = [9, 1, 5, 4, 3, 8, 7]
print(n_smallest(3, arr))
# 출력: 4

• 파이썬에서는 N번째로 작은 값을 구하는 메서드를 제공한다.
• nsmallest() 메서드는 가장 작은 n개의 값을 반환한다.

import heapq

arr = [9, 1, 5, 4, 3, 8, 7]
result = heapq.nsmallest(3, arr)
print(result[-1])
# 출력: 4

5.6.8 활용 예시 3 N번째로 큰 값

• 파이썬에서는 N번째로 큰 값을 구하는 메서드를 제공한다.
• nlargest() 메서드는 가장 큰 n개의 값을 반환한다.

import heapq

arr = [9, 1, 5, 4, 3, 8, 7]
result = heapq.nlargest(3, arr)
print(result[-1])
# 출력: 7

class Heap(object):
    def __init__(self):
        # 첫번째 원소는 사용하지 않음
        self.arr = [None]

    # 원소 삽입(push)
    def push(self, x):
        # 마지막 위치에 원소를 삽입
        self.arr.append(x)
        # 첫 원소인 경우 종료
        if len(self.arr) == 2:
            return
        # 값의 크기를 비교하며 부모를 타고 올라감
        i = len(self.arr) - 1
        while True:
            parent = i // 2
            # 작은 값을 부모 쪽으로 계속 이동
            if 1 <= parent and self.arr[parent] > self.arr[i]:
                self.arr[parent], self.arr[i] = self.arr[i], self.arr[parent]
                i = parent
            else:
                break

    # 원소 추출(pop)
    def pop(self):
        # 마지막 원소
        i = len(self.arr) - 1
        # 남은 원소가 없다면 종료
        if i < 1:
            return None
        # 루트 원소와 마지막 원소를 교체하여, 마지막 원소 추출
        self.arr[1], self.arr[i] = self.arr[i], self.arr[1]
        result = self.arr.pop()
        # 루트(root)에서부터 원소 정렬
        self.heapify()
        return result

    # 루트(root)에서부터 자식 방향으로 내려가며 재정렬
    def heapify(self):
        # 남은 원소가 1개 이하라면 종료
        if len(self.arr) <= 2:
            return
        # 루트 원소
        i = 1
        while True:
            # 왼쪽 자식
            child = 2 * i
            # 왼쪽 자식과 오른쪽 자식 중 더 작은 것을 선택
            if child + 1 < len(self.arr):
                if self.arr[child] > self.arr[child + 1]:
                    child += 1
            # 더 이상 자식이 없거나, 적절한 위치를 찾은 경우
            if child >= len(self.arr) or self.arr[child] > self.arr[i]:
                break
            # 원소를 교체하며, 자식 방향으로 내려가기
            self.arr[i], self.arr[child] = self.arr[child], self.arr[i]
            i = child

arr = [9, 1, 5, 4, 3, 8, 7]
heap = Heap()

for x in arr:
    heap.push(x)

while True:
    x = heap.pop()
    if x == None:
        break
    print(x, end=" ")
# 출력: 1 3 4 5 7 8 9

import random
import time


# N개의 무작위 데이터 생성
arr = []
n = 100000
for _ in range(n):
    arr.append(random.randint(0, 1000000))

# 시간 측정 시작
start_time = time.time()

# 힙에 모든 원소 삽입
heap = Heap()
for x in arr:
    heap.push(x)

# 힙에서 모든 원소 추출
result = []
while True:
    x = heap.pop()
    if x == None:
        break
    result.append(x)

# 시간 측정 종료
print(f"Elapsed time: {time.time() - start_time} seconds.")

# 오름차순 정렬 여부 확인
ascending = True
for i in range(n - 1):
    if result[i] > result[i + 1]:
        ascending = False
print("Sorted:", ascending)

# 가장 작은 5개 원소와 가장 큰 5개 원소 출력
print(result[:5])
print(result[-5:])
# 출력:
# Elapsed time: X.XXX seconds.  (실행 환경에 따라 다름)
# Sorted: True
# [최솟값 5개 (무작위 데이터로 매번 다름)]
# [최댓값 5개 (무작위 데이터로 매번 다름)]

6 응용 분야

• Dijkstra 최단 경로: 우선순위 큐로 현재 최단 거리의 노드를 \(O(\log N)\) 에 추출한다.
• Top-K 문제: 수백만 개 데이터에서 상위 K개 원소를 \(O(N \log K)\) 에 추출한다.
• 작업 스케줄링: 마감 시간이나 중요도에 따라 작업을 우선 처리한다.
• A* 탐색 알고리즘: f(n) = g(n) + h(n) 값이 낮은 노드를 우선 탐색하는 데 힙을 사용한다.
• 데이터 스트림 중앙값 유지: 최대 힙과 최소 힙 두 개로 동적 중앙값을 \(O(\log N)\) 에 갱신한다.

7 관련 주제

• 자료구조 개요
• 배열
• 연결 리스트
• 파이썬 리스트
• 스택
• 큐
• 덱
• 이진 탐색 트리
• 그래프