Skip to content

3주차 우선순위 큐, 힙

Jump to bottom
Dongjun Jeong edited this page Jan 26, 2023 · 4 revisions

1. 우선순위 큐, 그리고 힙

Priority Queue:

  • pop() 할 때 가장 먼저 들어온 원소가 나오는 대신 우선순위가 가장 높은 원소가 나오는 큐

    우리는 이걸 Priority Queue (우선순위 큐)라고 부르기로 사회적으로 약속했어요

Heap:

  • 데이터에서 최솟값 혹은 최댓값을 빠르게 찾기위해 고안된, 완전이진트리(Complete Binary Tree)를 기본으로 한 자료구조
Complete Binary Tree 노드를 채워갈 때, 최하단 왼쪽부터 차례대로 채워 나가는 이진트리

2. 시간복잡도

Priority Queue를 구현하는 방법은 여러가지 있겠으나, 시간복잡도를 고려하여 가장 효율적인 방식이 Heap 자료구조를 이용하는 것이다.

Action priority queue Array
삽입 O(logN) O(1)
(우선순위가 가장 높은 원소) 조회 O(1) O(N)
(우선순위가 가장 높은 원소) 제거 O(logN) O(N)

3. 핵심 로직

최대힙 기준

3.1 insert()

Untitled

https://visualgo.net/en/heap?slide=1-3

[15, 10, 8, 3, 20]

3.2 pop()

Untitled 1

4. 활용

4.1 PriorityQueue vs heapq

  • PriorityQueue 
    from queue import PriorityQueue

# 최소 힙으로 사용
min_heap = PriorityQueue()

min_heap.put(1)
min_heap.put(3)
min_heap.put(2)

print(min_heap.get()) # 1
print(min_heap.get()) # 2
print(min_heap.get()) # 3

# 우선순위 큐로 사용
priority_queue = PriorityQueue()
priority_queue.put([1, 'apple'])
priority_queue.put([3, 'banana'])
priority_queue.put([2, 'orange'])

print(priority_queue.get())  # [1, 'apple']
print(priority_queue.get())  # [2, 'orange']
print(priority_queue.get())  # [3, 'banana']
  • heapq 
    import heapq

# 최소 힙으로 사용
min_heap = []

heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 2)

print(heapq.heappop(min_heap))  # 1
print(heapq.heappop(min_heap))  # 2
print(heapq.heappop(min_heap))  # 3

# 우선순위 큐로 사용
priority_queue = []

heapq.heappush(priority_queue, [1, 'apple'])
heapq.heappush(priority_queue, [3, 'banana'])
heapq.heappush(priority_queue, [2, 'orange'])

print(heapq.heappop(priority_queue))  # [1, 'apple']
print(heapq.heappop(priority_queue))  # [3, 'banana']
print(heapq.heappop(priority_queue))  # [2, 'orange']

파이썬 우선순위 큐 구현에서 heapq가 PriorityQueue보다 실행시간이 적게 걸려 heapq를 일반적으로 많이 사용한다. 또한, PriorityQueue와 heapq는 최소 힙만 다룰 수 있기 때문에 큰 수부터 pop 하고싶을 때는 우선순위를 음수로 만들면 된다.

4.2 대표유형 풀이: [11279] 최대 힙

  • 문제 설명 Untitled 2
정답 코드 
import sys
import heapq

input = sys.stdin.readline

N = int(input())

priority_queue = []
for _ in range(N):
    value = int(input())

    if value == 0:
        max_node = heapq.heappop(priority_queue) if len(
            priority_queue) != 0 else (0, 0)
        print(max_node[1])
        continue

    node = (-1 * value, value)
    heapq.heappush(priority_queue, node)

5. 함께 공부할 문제 리스트

난이도 문제명 분류
[1927] 최소 힙 자료 구조 우선순위 큐
[11279] 최대 힙 자료 구조 우선순위 큐
[2075] N번째 큰 수 자료 구조 정렬 우선순위 큐
[1715] 카드 정렬하기 자료 구조 그리디 알고리즘 우선순위 큐
[11286] 절댓값 힙 자료 구조 우선순위 큐
[11000] 강의실 배정 자료 구조 그리디 알고리즘 우선순위 큐 정렬
[1655] 가운데를 말해요 자료 구조 우선순위 큐
[2696] 중앙값 구하기 자료 구조 우선순위 큐
[1781] 컵라면 자료 구조 그리디 알고리즘 우선순위 큐
Lv.2 더 맵게 프로그래머스 고득점 KIT 힙(Heap)
Lv.3 디스크 컨트롤러 프로그래머스 고득점 KIT 힙(Heap)
Clone this wiki locally