힙과 우선순위 큐 2

힙과 우선순위 큐에서 본 힙(heap)의 넣기·꺼내기를 바탕으로, 원소 여러 개로 힙을 한 번에 만드는 방법과 힙으로 하는 정렬을 이어서 다룬다. 그다음 우선순위 큐(priority queue)를 왜 힙으로 만드는지와 대표 활용을 보고, 비슷한 일을 할 수 있는 트리(tree)와 비교한다.

힙 만들기는 O(n)

원소 n개로 힙을 만들 때 하나씩 넣으면 O(n log n)이다. 빅오 표기법(Big-O notation)으로 적은 이 값은 n이 커질 때 걸리는 시간이 얼마나 빨리 늘어나는지를 나타낸다. 더 빠른 방법은 배열(array)을 그대로 두고, 자식이 있는 마지막 노드(node)부터 루트 노드(root node)까지 거꾸로 가며 노드마다 아래로 내리기(sift down)를 하는 것이다. 아래로 내리기는 부모와 자식의 크기 규칙이 맞을 때까지 노드를 자식과 바꾸며 내려보내는 동작이다. 노드의 절반쯤은 리프 노드(leaf node)라 할 일이 없고, 아래쪽 노드일수록 내려갈 거리가 짧다. 이 비용을 다 더하면 O(n)이 된다. Python의 heapq.heapify가 이 방식으로 선형 시간(O(n), 원소 수에 비례하는 시간)에 힙을 만든다.

힙 정렬

힙 정렬(heapsort)은 배열로 최대 힙(max heap)을 만든 뒤(O(n)), 루트(최댓값)를 배열 맨 끝 원소와 바꾸고, 힙 크기를 하나 줄인 뒤 루트로 올라온 원소를 아래로 내린다. 이 과정을 힙이 빌 때까지 반복한다. 끝에서부터 큰 값이 차례로 쌓여 오름차순 정렬이 된다. 최악에도 O(n log n)이고 배열 안에서 자리만 바꾸므로 추가 메모리가 O(1)이다. 대신 루트와 맨 끝 원소처럼 멀리 떨어진 칸끼리 자리를 바꾸므로, 같은 값 두 개가 있으면 뒤에 있던 것이 앞으로 건너뛸 수 있다. 그래서 같은 값의 원래 순서를 지키지 않는 불안정 정렬(unstable sort)이다.

우선순위 큐와 활용

우선순위 큐는 "넣기"와 "가장 우선인 것 꺼내기"를 제공하는 개념이고, 힙은 그 개념을 만드는 방법 중 하나다. 정렬된 배열로 만들면 꺼내기는 O(1)이지만 넣을 자리를 만들려고 원소를 밀어야 해서 넣기가 O(n)이다. 정렬 안 된 배열이면 반대로 넣기는 끝에 붙이는 O(1)이지만, 꺼낼 때마다 전체를 훑어 가장 우선인 것을 찾아야 해서 O(n)이다. 힙으로 만들면 둘 다 O(log n)이라 균형이 좋다. Java의 PriorityQueue는 기본이 최소 힙(min heap)이다. 공식 문서는 넣기·꺼내기(offer·poll)를 O(log n), 맨 앞 보기(peek)를 상수 시간, 임의 원소 찾기·삭제(contains·remove(Object))를 선형 시간이라고 적고 있다.

• 작업 스케줄링: 마감이 가장 급하거나 우선순위가 가장 높은 작업을 먼저 꺼내 처리한다.
• 다익스트라 알고리즘(Dijkstra's algorithm): 최단 거리를 구할 때 "지금까지 가장 가까운 정점(vertex)"을 반복해서 꺼낸다. 자세한 것은 그래프 2에서 다룬다.
• Top-K(상위 K개 구하기): n개 중 가장 큰 K개를 구할 때 크기 K의 최소 힙을 유지한다. 최소 힙의 맨 위는 지금까지 고른 K개 중 가장 작은 값, 즉 탈락 후보이므로 새 값과 이것 하나만 비교하면 된다. 새 값이 더 크면 바꿔 넣는다. 전체 정렬 O(n log n) 대신 O(n log K)로 끝난다.

힙과 이진 탐색 트리

이진 탐색 트리(binary search tree)도 최솟값을 찾을 수 있고, 왼쪽 서브트리(subtree), 자기 자신, 오른쪽 서브트리 순서로 도는 중위 순회(inorder traversal)로 모든 값을 정렬 순서대로 읽을 수도 있다. 그래도 두 구조가 잘하는 일은 다르다. 아래 표의 이진 탐색 트리는 넣고 뺄 때 스스로 높이를 낮게 유지하는 균형 트리(balanced tree)를 기준으로 한다. 균형이 깨져 한쪽으로 늘어지면 찾기가 O(n)까지 느려진다.

기준	힙	균형 이진 탐색 트리
최솟값(또는 최댓값) 확인	O(1)	O(log n)
넣기·최솟값 꺼내기	O(log n)	O(log n)
임의 값 찾기	O(n)	O(log n)
정렬 순서로 전부 읽기	불가(꺼내며 정렬해야 함)	중위 순회로 O(n)
메모리	배열 하나, 포인터(pointer) 없음	노드마다 포인터

"가장 우선인 것만 계속 꺼내면 된다"면 힙이 가볍고 빠르다. 임의 값 찾기나 범위 찾기가 필요하면 트리와 이진 탐색 트리 2의 이진 탐색 트리를 쓴다.

면접 포인트

• "힙 만들기 복잡도는?" → 바닥부터 아래로 내리기로 만들면 O(n). 하나씩 넣으면 O(n log n).
• "힙 정렬의 특징은?" → 최악에도 O(n log n), 추가 메모리 O(1), 불안정 정렬.
• "우선순위 큐 활용은?" → 작업 스케줄링, 다익스트라, Top-K(크기 K 최소 힙, O(n log K)).
• "힙 vs 이진 탐색 트리" → 최솟값만 계속 꺼내면 힙(확인 O(1), 배열 하나). 임의 값·범위 찾기가 필요하면 균형 이진 탐색 트리.