가장 급한 일을 먼저 꺼낼 때 목록을 매번 정렬해야 할까?

작업 네 건의 우선순위가 5, 2, 8, 4라고 하자. 숫자가 작을수록 급하다면 지금은 2를 먼저 처리해야 한다. 잠시 뒤 우선순위 1인 작업이 새로 들어올 수도 있다. 급한 작업 하나를 꺼낼 때마다 목록 전체를 정렬하는 방법도 있지만, ‘다음에 처리할 한 건’을 빨리 찾는 데 맞춘 구조를 쓸 수 있다.

우선순위 큐(priority queue)는 들어온 순서와 관계없이 우선순위가 가장 높은 값을 먼저 꺼내는 자료구조다. 앞에서 본 일반 큐(queue)가 먼저 들어온 것을 먼저 꺼내는 것과 다르다. 우선순위 큐를 구현하는 방법 중 하나가 힙(heap)이다. 힙은 전체 원소를 차례대로 정렬하지 않고, 다음에 꺼낼 값이 맨 앞에 오도록 필요한 관계만 유지한다.

맨 앞이 최솟값인 이유

최소 힙(min-heap)은 부모의 값이 자식의 값보다 크지 않다는 규칙을 지키는 나무 모양의 구조다. 부모와 자식만 비교하므로 맨 위에는 전체에서 가장 작은 값이 온다.

        2
      /   \
     5     4
    / \   /
   9   7  8

위에서 2 ≤ 5, 2 ≤ 4, 5 ≤ 9, 5 ≤ 7, 4 ≤ 8이다. 하지만 5와 4 사이에는 순서 약속이 없다. 7보다 8이 큰데도 왼쪽과 오른쪽의 위치만 보고 순서를 읽을 수 없다. 힙의 맨 위는 최솟값이지만, 힙 전체가 정렬된 목록은 아니다.

이런 모양을 트리(tree)라고 한다. 트리는 값이 들어 있는 노드(node)와 노드를 잇는 간선(edge)으로 관계를 표현한다. 힙에는 보통 각 노드의 자식이 최대 둘이고 마지막 줄을 왼쪽부터 채우는 완전 이진 트리(complete binary tree)를 쓴다. 중간에 빈칸이 없으므로 배열에 차례대로 담을 수 있다. 배열은 값을 번호가 붙은 칸에 순서대로 담는 자료구조다.

배열에서 0번 칸을 맨 위로 놓으면 i번 칸의 왼쪽 자식은 2i+1, 오른쪽 자식은 2i+2에 있다. 위 그림을 [2, 5, 4, 9, 7, 8]로 담을 수 있다. 실제로 나무 모양의 객체를 모두 따로 만들지 않아도 부모와 자식 관계를 계산할 수 있다는 뜻이다.

새 작업이 들어오면 어디에 놓나

위 배열에 우선순위 1인 작업을 추가한다. 먼저 마지막 칸에 넣어 완전 이진 트리의 모양을 지킨다. 그 뒤 부모보다 값이 작으면 자리를 바꾸며 위로 올린다.

추가 직후:  [2, 5, 4, 9, 7, 8, 1]
4와 교환:  [2, 5, 1, 9, 7, 8, 4]
2와 교환:  [1, 5, 2, 9, 7, 8, 4]

마지막에는 1이 맨 위에 온다. 한 단계 올라갈 때마다 부모 쪽으로 이동하므로 방문하는 칸 수는 트리의 높이를 넘지 않는다. 원소가 n개일 때 높이는 대략 log n에 비례한다. 빅오(Big-O notation)는 입력 크기가 커질 때 작업량이 얼마나 늘어나는지 나타낸다. 이 표기로 삽입은 O(log n)이다.

최솟값을 꺼낸 뒤에는 빈자리를 어떻게 채우나

맨 위의 1을 꺼내면 마지막 값 4를 맨 위로 옮긴다. 이제 부모가 자식보다 작아야 한다는 규칙이 깨질 수 있다. 둘 중 작은 자식과 비교하며 아래로 내려 보낸다.

꺼내기 전:       [1, 5, 2, 9, 7, 8, 4]
1 꺼내고 4 이동: [4, 5, 2, 9, 7, 8]
2와 교환:       [2, 5, 4, 9, 7, 8]

다시 2가 맨 위에 왔다. 최솟값만 확인한다면 맨 앞 한 칸을 읽으면 되므로 O(1)이다. 최솟값을 꺼내고 힙 규칙을 복구하는 데는 O(log n)이 든다.

그렇다면 주문 번호 42가 힙 안에 있는지도 빨리 찾을 수 있을까? 그렇지 않다. 힙은 부모와 자식 사이의 우선순위만 약속한다. 현재 노드의 값보다 찾는 값이 크다고 해서 반드시 왼쪽 또는 오른쪽 한쪽에만 있다고 말할 수 없다. 임의의 번호를 찾는 일은 많은 칸을 확인해야 할 수 있다. 번호 조회가 많다면 번호를 빠르게 찾는 별도의 자료구조가 필요하다.

우선순위가 같은 작업은 무엇을 먼저 할까

작업 A와 B의 우선순위가 모두 2라면 최소 힙 규칙만으로는 둘 중 누가 먼저 나올지 정해지지 않는다. 접수 순서까지 지켜야 한다면 (우선순위, 접수 순번)을 묶어 비교할 수 있다. 우선순위가 같을 때 먼저 받은 작업의 순번이 작으므로 먼저 꺼낸다.

작업이 들어온 뒤 우선순위가 바뀌거나 취소될 수도 있다. 이때 힙에서 해당 작업을 직접 찾아 고치려면 그 작업이 몇 번 칸에 있는지도 관리해야 한다. 그렇지 않으면 취소 표식을 남겨 두고 맨 위로 나왔을 때 건너뛰는 방식 등을 선택할 수 있지만, 쌓인 표식을 언제 정리할지도 필요하다. ‘다음 한 건을 빨리 꺼낸다’는 장점이 모든 변경 작업을 자동으로 쉽게 만드는 것은 아니다.

우선순위가 높은 작업이 계속 들어오면 낮은 작업은 오랫동안 나오지 못할 수 있다. 힙은 입력된 숫자의 순서를 지킬 뿐, 오래 기다린 작업을 알아서 배려하지 않는다. 일정 시간 기다린 작업의 우선순위를 높일지, 긴급 작업에 하루 처리량의 일부만 배정할지 같은 운영 규칙은 따로 정해야 한다. 그 규칙이 바뀌면 힙 안에 이미 들어 있는 값의 우선순위도 갱신해야 할 수 있다.

작업이 네 건인 경우에는 배열 전체에서 최솟값을 찾는 데 최대 네 건만 보면 된다. 매번 최솟값을 꺼내야 하고 작업이 수십만 건까지 늘어난다면 매번 전체를 확인하는 비용이 커진다. 작업이 거의 없고 순서 변경도 드물다면 힙을 유지하는 코드가 불필요하게 복잡할 수 있다. 최솟값 확인·삽입·꺼내기가 자주 일어나는 작업 대기열에서 힙의 장점이 드러난다.

전체 정렬은 결과의 모든 순서가 필요할 때 맞는다. 최소 힙은 새 작업이 계속 들어오는 동안 현재 가장 급한 한 건을 반복해서 꺼내야 할 때 맞는다. 어느 작업이 더 많은지에 따라 목록을 정렬해 둘지, 힙을 유지할지, 번호 검색용 구조를 따로 둘지 달라진다.

참고 자료

• Python 문서의 힙과 우선순위 큐 설명
• Python 문서의 정렬과 부분 정렬 비교