힙과 우선순위 큐(Heap and priority queue)

응급실은 먼저 온 순서가 아니라 급한 순서로 환자를 봅니다. 이렇게 '가장 급한 것 꺼내기'와 '새 것 넣기'를 되풀이하는 자료 구조가 우선순위 큐입니다. 목록을 늘 정렬된 채로 두면 새 것을 제자리에 끼워 넣는 데, 정렬하지 않고 두면 가장 작은 것을 처음부터 찾는 데 n에 비례하는 시간이 듭니다. 힙⁠(heap)⁠을 쓰면 두 조작 모두 $O(\log n)$이면 됩니다.

(최소) 힙은 모든 부모가 자식보다 작거나 같은 이진 트리⁠(tree)⁠입니다. 형제끼리의 순서는 따지지 않으니 정렬보다 훨씬 느슨한 조건이지만, 가장 작은 원소⁠(element)⁠가 늘 뿌리에 있다는 것만은 보장됩니다. 트리를 위층부터, 한 층 안에서는 왼쪽부터 빈틈없이 채우므로 연결을 따로 적을 필요 없이 배열 하나에 층별로 적으면 되고, i번 칸의 자식은 2i+1번과 2i+2번 칸에 있습니다. n개가 들어 있으면 높이는 $\lfloor \log_2 n \rfloor$입니다.

넣기 가장 작은 것 꺼내기 처음으로

넣을 때는 새 원소를 맨 끝 빈자리에 두고, 부모보다 작으면 자리를 바꾸며 올라갑니다. 꺼낼 때는 뿌리를 가져가고, 맨 끝 원소를 뿌리에 올린 뒤 두 자식 중 작은 쪽보다 크면 자리를 바꾸며 내려갑니다. 어느 쪽이든 한 층에 비교 한두 번이니 모두 높이의 두 배 이하, 곧 $O(\log n)$입니다(로그). 지금까지 꺼낸 값: . 그사이 더 작은 값을 새로 넣지 않는 한 꺼낸 값은 작아지지 않는 순서로 나옵니다(같은 값이 있으면 나란히 나옵니다). n개를 넣었다가 모두 꺼내면 정렬이 되니, 이것이 $O(n \log n)$ 힙 정렬입니다(1964년 영국 출신의 컴퓨터 과학자 J. W. J. 윌리엄스가 발표했습니다).

이어지는 곳. 변의 길이가 음수가 아닌 그래프에서 데이크스트라가 만든 다익스트라 최단 경로⁠(shortest path)⁠ 알고리즘⁠(algorithm)⁠은 '아직 확정하지 않은 점 가운데 가장 가까운 점'을 힙에서 꺼내고, 1957년 로버트 프림이 발표한 최소 신장 트리⁠(minimum spanning tree)⁠ 알고리즘도 지금 트리에 가장 가까운 점을 힙에서 꺼냅니다. 허프만 부호⁠(Huffman coding)⁠는 가장 드문 두 기호를 힙에서 꺼내 묶은 뒤 다시 넣기를 되풀이하는 욕심쟁이 알고리즘⁠(greedy algorithm)⁠입니다. 최대 힙과 최소 힙을 하나씩 두면 값이 계속 들어오는 동안에도 중앙값⁠(median)⁠을 곧바로 읽을 수 있고, 시뮬레이션에서는 다음에 일어날 사건⁠(event)⁠을 시각순으로 꺼내는 데 씁니다. 배열 번호를 1부터 매기면 i번 칸의 부모는 i를 이진법⁠(binary)⁠으로 쓰고 마지막 자리를 지운 수입니다. 예를 들어 6은 이진법으로 110이고, 마지막 자리를 지운 11은 3이므로 6번 칸의 부모는 3번 칸입니다.