비교
교환
꺼낸 값

  • 내리는 중
  • 비교 중
  • 교환됨
  • 제자리

힙 정렬 자세히 알아보기

힙 정렬

힙 정렬은 목록을 이진 트리로 읽고, 모든 부모가 자식보다 크거나 같은 최대 힙으로 재배열합니다. 그러면 가장 큰 값이 맨 위에 옵니다. 이 값을 끝으로 교환해 그 자리에 두고, 힙을 복구한 뒤 반복합니다. 앱은 막대 위에 힙을 트리로 그려 주므로, 각 값이 아래로 내려가는 과정을 따라갈 수 있습니다. ‘재생’을 눌러 정렬을 보거나, ‘단계’와 ‘뒤로’로 비교를 하나씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 막대 위의 트리는 같은 값을 힙으로 보여 줍니다. 타일에는 비교, 교환 횟수와 힙에서 꺼낸 값의 수가 표시됩니다. 막대 개수와 시작 순서를 고르거나 직접 숫자를 입력하세요. 보드를 선택한 상태에서는 화살표 키로 한 단계씩 이동하고, 스페이스 바로 재생과 일시 정지를 하며, Home과 End로 처음과 끝으로 이동합니다.

작동 원리

  1. 막대 개수와 시작 순서를 고르세요: 무작위, 거의 정렬됨, 역순, 값 종류 적음. 직접 숫자를 입력해도 됩니다.
  2. ‘재생’을 누르거나, ‘단계’와 ‘뒤로’로 비교를 하나씩 진행하세요. 단계 슬라이더를 끌면 정렬의 원하는 지점으로 이동합니다.
  3. 트리를 지켜보세요. 먼저 힙이 완성될 때까지 모든 부모가 아래로 내려가고, 그다음 루트가 끝으로 교환되며 힙이 하나씩 줄어듭니다.

힙 정렬의 원리

목록을 트리로 읽습니다. 위치 i의 값은 위치 2i + 1과 2i + 2에 자식이 있습니다. 마지막 부모부터 시작해 모든 부모를 아래로 내려 최대 힙을 만듭니다. 어떤 값이 더 큰 자식보다 작은 동안 둘을 교환합니다. 루트에 가장 큰 값이 오면 힙의 마지막 값과 교환합니다. 그 값은 이제 확정되고, 힙은 하나 짧아지며, 새 루트를 아래로 내려 다시 힙으로 만듭니다. 힙이 빌 때까지 반복합니다.

언제나 n log n, 제자리 정렬

트리는 약 log₂ n층이므로 아래로 내리기 한 번은 많아야 약 2 log₂ n번 비교하고, 힙을 만드는 데는 2n번보다 적게 비교합니다. 그래서 힙 정렬은 최악의 경우에도 약 2n log₂ n번 비교하며 버퍼가 필요 없습니다. 값이 40개면 많아야 352번입니다. 퀵 정렬과 달리 불리한 입력이 없고, 병합 정렬과 달리 추가 메모리가 필요 없습니다. 실제로는 목록 여기저기를 오가기 때문에 보통 둘 다보다 느리고, 안정 정렬도 아닙니다.

자주 묻는 질문

힙 정렬은 어떻게 동작하나요?

목록을 최대 힙으로 바꿉니다. 최대 힙은 목록 안에 저장된 트리로, 모든 부모가 자식보다 크거나 같습니다. 그런 다음 루트에 있는 가장 큰 값을 힙의 끝으로 교환하고, 새 루트를 아래로 내려 힙을 복구하는 일을 반복합니다.

힙이란 무엇인가요?

포인터 없이 목록에 저장된 완전 이진 트리입니다. 위치 i의 자식은 위치 2i + 1과 2i + 2입니다. 최대 힙에서는 모든 부모가 자식보다 크거나 같으므로, 가장 큰 값은 항상 루트, 즉 위치 0에 있습니다.

힙을 만드는 일은 왜 빠른가요?

대부분의 값은 트리 아래쪽에 있어서 한두 층만 내려갈 수 있습니다. 모든 층의 작업을 더하면 힙 전체를 만드는 데 n log n이 아니라 2n번보다 적은 비교가 듭니다.

힙 정렬은 안정 정렬인가요?

아닙니다. 루트를 끝으로 교환하면 값이 먼 거리를 이동하므로, 같은 값의 순서가 바뀔 수 있습니다.

제 숫자가 어딘가로 전송되나요?

아니요. 정렬은 브라우저에서 실행되며, 마지막 설정은 이 브라우저의 로컬 저장소에 남습니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

편집기로 이동