9 / 14강

힙과 우선순위

예약된 작업 가운데 마감이 가장 가까운 일부터 처리하려 합니다. 새 작업은 계속 들어옵니다. 그때마다 전체를 정렬하지 않고도 가장 먼저 처리할 항목을 빠르게 꺼내는 구조가 있으면 좋겠습니다.

우선순위 큐와 힙

우선순위 큐는 우선순위가 가장 높은 항목을 꺼내는 자료형입니다. 이를 구현하는 대표적인 자료구조가 이진 힙입니다.

• 모양: 마지막 층을 제외하면 채워져 있고, 마지막 층도 왼쪽부터 채운 완전 이진 트리입니다.
• 최소 힙의 규칙: 부모의 값이 자식의 값보다 작거나 같습니다. 최솟값은 루트에 있습니다.
• 최대 힙: 반대로 부모가 자식보다 크거나 같아서 최댓값이 루트에 옵니다.

힙은 전체가 정렬된 배열은 아닙니다. 형제끼리의 순서는 정하지 않습니다. 최소 힙에서 두 번째 칸이 반드시 두 번째로 작은 값인 것도 아닙니다.

배열에 담는 방법

0번 칸을 루트로 쓰면 i번 노드의 자식은 2*i+1, 2*i+2번입니다. 루트 이외 노드의 부모는 (i-1)//2번입니다. 꽉 채우는 모양 덕분에 별도 연결 없이 위치로 관계를 표현합니다.

추가할 때는 마지막 칸에 넣고 부모와 비교하며 올립니다. 최솟값을 꺼낼 때는 마지막 항목을 루트로 옮긴 뒤 자식과 비교하며 내립니다. 높이에 비례하므로 각각 O(log n)입니다. 최솟값을 보기만 하는 일은 O(1)입니다.

마감이 가까운 작업 꺼내기

import heapq

jobs = []
heapq.heappush(jobs, (3, "backup"))
heapq.heappush(jobs, (1, "reply"))
heapq.heappush(jobs, (2, "review"))

while jobs:
    print(heapq.heappop(jobs)[1])

숫자가 작을수록 먼저 처리하므로 reply, review, backup 순서입니다. 튜플은 앞의 값을 먼저 비교합니다. 우선순위가 같으면 뒤의 작업 이름을 비교하므로, 접수 순서까지 지키려면 증가하는 접수 번호를 두 번째 값으로 넣어야 합니다.

확인 문제

최소 힙에 있는 모든 값을 heappop으로 꺼내면 어떤 순서가 될까요? 단순히 힙 배열을 앞에서부터 읽는 것과 같을까요?

Python 공식 문서: heapq