[자료구조] 우선순위 큐(priority queue) 와 힙(Heap)

 

이전에 스택과 큐에 대해서 정리했었는데,

이번에는 우선순위 큐(priority queue)와 힙(Heap)은 각자 무엇인지, 이 둘은 어떤 관계가 있는지 알아보고자 한다. 

 

 

1. 우선순위 큐(priority queue)

우선순위가 높은 원소가 먼저 나오는 큐

• 일반 큐: FIFO(First In, First Out)
• 우선순위 큐: 삽입 순서와 무관하게 항상 우선순위가 높은 원소가 먼저 삭제

즉, 삽입할 때는 그냥 넣을 수 있지만, 삭제(Dequeue)할 때는 항상 우선순위가 가장 높은 원소가 나오도록 보장한다.

 

• 기본 컨테이너 : 배열, 연결리스트, 힙

 

 

1-1. 우선순위 큐에 요구되는 멤버함수

• 삽입/삭제 시 우선순위를 비교해야 하므로, 내부 컨테이너는 원소 순서를 관리할 수 있어야 함

멤버 함수	역할
Insert / Push	새 원소 삽입
DeleteMax / DeleteMin	가장 높은/낮은 우선순위 원소 제거 및 반환
FindMax / FindMin	가장 높은/낮은 우선순위 원소 조회
IsEmpty	큐가 비어 있는지 확인
Size (선택)	큐에 들어 있는 원소 개수 확인

 

1-2. 구현 방법 및 시간 복잡도

• 구현에 배열 사용하면?
  • 정렬 안 하는 배열을 사용할 때 최악 시간 복잡도
    • 삽입: 제일 뒤에 추가 하므로 O(1)
    • 삭제: 우선 순위가 높은 요소를 순차적으로 찾으므로 O(n) + 삭제 후 이동 O(n) = O(n)
  • 정렬 하는 배열을 사용할 때 최악 시간 복잡도
    • 삽입: 삽입할 위치 찾기는 절반씩 나눠찾으므로 O(log2n) + 삭제 후 이동 O(n) = O(n)
    • 삭제: 우선순위가 높은 것이 제일 뒤 이므로 이동 없음 O(1)

 

• 구현에 연결리스트 사용하면? 
  • 정렬 안 하는 배열을 사용할 때의 최악 시간 복잡도
    • 삽입: 빠르게 제일 앞에 추가 하므로 O(1)
    • 삭제: 우선 순위가 높은 요소를 순차적으로 찾으므로 O(n)
  • 정렬 하는 배열을 사용할 때의 최악 시간 복잡도
    • 삽입:  삽입 할 위치 찾기는 순차적으로 찾으므로 O(n)
    • 삭제: 우선순위가 높은 것이 앞이므로 이동 없음 O(1)

구현 방법	삽입	삭제
배열 (정렬 안 함)	O(1)	O(n)	삭제 시 우선순위 검색 필요
배열 (정렬 함)	O(n)	O(1)	삽입 시 위치 검색 필요
연결리스트 (정렬 안 함)	O(1)	O(n)	삽입 빠름, 삭제 시 순차 검색
연결리스트 (정렬 함)	O(n)	O(1)	삭제 빠름, 삽입 시 순차 검색
힙(Heap)	O(log n)	O(log n)	최댓값/최솟값 접근 O(1), 효율적

 

 

2-3. 우선순위 큐의 활용

 

“우선순위가 높은 것부터 꺼내자” 를 활용

 

 

1. 운영체제(OS)에서의 우선순위 큐 활용 

• 프로세스 스케줄링:
  • CPU에 할당할 프로세스 우선순위 관리 (예: Ready Queue)
• 입출력(I/O) 관리:
  • 프린터, 디스크 요청 처리 순서 관리 (예: Printer Queue)
• 작업 대기열(Job/Task Queue):
  • 준비 상태인 작업 순서대로 CPU 할당

 

2. 프로그래밍에서의 우선순위 큐 활용 

• 이벤트 처리:
  • GUI, 게임 엔진 등에서 이벤트 순서 관리
• 멀티스레드 프로그래밍:
  • Producer-Consumer 문제에서 안전한 데이터 전달
• 네트워크 패킷 처리:
  • 수신/송신 패킷 순서 관리
• 버퍼 관리:
  • 오디오/비디오, 센서 데이터 등 순차적 처리

 

 

 

2. 힙(Heap) 

완전 이진 트리를 기반으로 한 자료구조, 우선순위 큐를 효율적으로 구현하기 위해 사용

• 특징: 느슨한 정렬 상태 유지, 루트 노드 값만 의미 있음

 

2-1. 힙의 종류

종류	규칙	특징
최대 힙(Max Heap)	부모 ≥ 자식	루트에 가장 큰 값 위치
최소 힙(Min Heap)	부모 ≤ 자식	루트에 가장 작은 값 위치

 

 

2-2. 힙의 구현 : 배열 

• 배열에서 힙 인덱스 규칙
  • 구현 편의상 index = 0 사용 안함. 배열에서 인덱스 1부터 시작한다고 가정한다. 

관계	계산식
부모 노드	parent = child / 2
왼쪽 자식	leftChild = parent * 2
오른쪽 자식	rightChild = parent * 2 + 1

 

• 배열에서 힙 연산
  •  

연산
삽입	배열 뒤에 추가 → 부모와 비교 → 위로 올림 (Heapify Up)
	=> 배열 제일 뒤에 넣고 부모 노드와 비교 후 교환 하기
삭제	루트 제거 → 배열 마지막 노드를 루트에 넣고 → 자식과 비교 → 아래로 내림 (Heapify Down)
	=> 배열의 제일 뒤를 루트에 넣고 비교 후 교환 하기

 

 

 

 

4. 정리 

 

• 우선순위 큐: 우선순위 높은 원소 먼저 삭제 (개념)
• 힙: 우선순위 큐 효율적 구현 (자료구조)
• STL priority_queue를 활용하면 간단하게 사용 가능