힙 정렬
힙 정렬은 가장 큰 값을 더 잘 찾는 방법을 쓰는 선택 정렬입니다. 정렬되지 않은 값을 힙에 둡니다. 힙은 목록 안에 저장된 트리로, 가장 큰 값이 항상 맨 위에 있습니다. 그 값을 꺼내고 힙을 복구하는 데는 전체를 훑는 대신 약 log n단계면 됩니다.
목록 안의 트리
이진 힙은 포인터가 필요 없는 트리입니다. 위치 0이 루트이고, 위치 i의 자식은 위치 2i + 1과 2i + 2입니다. 따라서 위치 1과 2는 루트의 자식, 위치 3부터 6까지는 다음 층이 되는 식입니다. 마지막 층을 뺀 모든 층은 꽉 차 있고, 마지막 층은 왼쪽부터 채워집니다. 최대 힙에서는 모든 부모가 자식보다 크거나 같으므로, 가장 큰 값은 항상 루트에 있습니다.
아래로 내리기
모든 일을 연산 하나가 합니다. 값을 아래로 내리려면 그 값을 자식과 비교합니다. 더 큰 자식이 그 값보다 크면 둘을 교환하고, 그 값을 새 자식과 비교합니다. 더 큰 자식이 없거나 맨 아래에 닿으면 멈춥니다. 트리는 약 log₂ n층뿐이므로 아래로 내리기 한 번은 많아야 약 2 log₂ n번 비교합니다.
힙을 만든 뒤 정렬하기
힙을 만들려면 마지막 부모부터 루트까지 거슬러 올라가며 모든 부모를 아래로 내립니다. 각 하위 트리는 그 부모가 내려오기 전에 이미 힙입니다. 그다음 정렬합니다. 루트, 즉 가장 큰 값을 힙의 마지막 값과 교환합니다. 그 값은 이제 최종 위치에 있습니다. 힙은 하나 짧아지고, 루트에 온 값을 아래로 내려 힙을 복구합니다. 값이 하나 남을 때까지 반복합니다.
예시
5, 1, 4, 2, 8을 예로 들어 보겠습니다. 힙을 만들 때 1이 8 아래로 내려가고, 이어서 5가 8 아래로 내려가 8, 5, 4, 2, 1이 됩니다. 이제 8이 끝으로 교환되고, 1이 루트에 와서 5와 2를 지나 내려갑니다: 5, 2, 4, 1 | 8. 그다음 5가 끝으로 가고 1이 4를 지나 내려갑니다: 4, 2, 1 | 5, 8. 두 번 더 하면 정렬이 끝납니다: 1, 2, 4, 5, 8. 비교 12번, 교환 10번입니다.
장점과 단점
힙 정렬은 최악의 경우에도 n log n에 비례하는 시간이 걸리고, 추가 메모리가 필요 없습니다. 퀵 정렬은 n²까지 느려질 수 있고 병합 정렬은 목록만큼 긴 버퍼가 필요하므로, 힙 정렬은 안전한 대안입니다. C++ 표준 라이브러리가 쓰는 introsort는 퀵 정렬의 분할이 잘못되면 힙 정렬로 바꿉니다. 실제 컴퓨터에서는 목록의 먼 위치 사이를 오가기 때문에 보통 둘 다보다 느리고, 안정 정렬도 아닙니다. J. W. J. Williams가 1964년에 이진 힙과 함께 힙 정렬을 발표했습니다.
직접 해 보기
앱을 열고 ‘단계’를 누르세요. 막대 위의 트리가 힙을 보여 줍니다. 아래로 내려가는 값은 고유한 색으로 표시되고, 비교 중인 자식은 강조되며, 모든 교환이 트리와 막대 양쪽에 나타납니다. 힙이 완성되면 루트가 끝으로 교환되어 초록색이 되고 트리에서 빠지는 모습을 지켜보세요.
자주 묻는 질문
힙 정렬의 시간 복잡도는 얼마인가요?
최선, 평균, 최악의 경우 모두 O(n log n)입니다. 힙을 만드는 데 O(n), n − 1번의 꺼내기에 각각 O(log n)이 걸립니다. O(1)의 추가 메모리로 제자리에서 정렬합니다.
힙 정렬과 선택 정렬은 무엇이 다른가요?
둘 다 남은 값 중 가장 큰(또는 가장 작은) 값을 거듭 꺼냅니다. 선택 정렬은 정렬되지 않은 부분을 전부 훑어서 찾으므로 매번 n번 비교합니다. 힙 정렬은 정렬되지 않은 부분을 힙에 두어 가장 큰 값이 이미 맨 위에 있고, 힙 복구에는 약 log n번의 비교만 듭니다.
힙은 정렬 말고 어디에 쓰이나요?
우선순위 큐입니다. 힙은 가장 큰(또는 가장 작은) 항목을 바로 알려 주고, 항목을 약 log n단계에 추가하거나 제거할 수 있게 해 줍니다. 스케줄러, Dijkstra의 최단 경로 알고리즘, 이벤트 시뮬레이션이 모두 힙을 씁니다.
힙 정렬은 안정 정렬인가요?
아닙니다. 루트를 끝으로 교환하면 값이 먼 거리를 이동하므로, 같은 값끼리 순서가 바뀔 수 있습니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
힙 정렬 해 보기