제자리 힙 정렬: 배열 heapify와 확정 구간의 경계

제자리 힙 정렬은 입력 배열 자체를 최대 힙으로 만든 뒤, 최댓값을 오른쪽 끝에 하나씩 확정합니다. 아직 힙인 앞 구간과 정렬이 끝난 뒤 구간의 경계를 지키는 것이 핵심입니다.

선수 지식: 배열 인덱스·완전 이진 트리·힙 부모 자식 관계

• 배열의 부모·자식 인덱스로 최대 힙 만들기
• heapify가 아래에서 위로 진행하는 이유 설명하기
• 동일 배열을 반환하는 제자리 정렬과 불안정성 이해하기

배열 앞부분을 최대 힙으로 해석합니다

최대 힙은 각 부모 값이 자식 값 이상인 완전 이진 트리입니다. 0부터 시작하는 배열에서는 부모 i의 왼쪽 자식이 2i+1, 오른쪽 자식이 2i+2입니다. 루트 0에는 최댓값이 있지만, 형제나 서로 다른 가지 전체가 오름차순인 것은 아닙니다. 그래서 힙을 만들었다는 사실과 정렬이 끝났다는 사실을 구분해야 합니다.

이 예제의 siftDown은 현재 부모와 더 큰 자식을 비교합니다. 자식이 더 크면 두 값을 바꾸고 그 자식 위치에서 계속 내려갑니다. 작은 자식과 바꾸면 다른 큰 자식이 부모보다 커서 힙 조건이 남을 수 있으므로 반드시 두 자식 중 큰 쪽을 먼저 고릅니다. size는 배열 전체 길이가 아니라 현재 힙으로 다루는 앞 구간의 길이입니다. 자식 인덱스가 size 이상이면 이미 확정된 뒤 구간에 속하므로 읽지 않습니다.

마지막 부모부터 고쳐 heapify를 완성합니다

잎은 자식이 없으므로 혼자서 이미 힙입니다. 마지막 부모인 floor(N/2)-1부터 0까지 거꾸로 내려가며 siftDown을 적용하면, 현재 부모를 고칠 때 그 자식 아래는 이미 힙입니다. 자식 쪽의 조건을 먼저 완성하는 순서가 있어야 한 번 내려가는 작업만으로 현재 부분 트리도 고칠 수 있습니다. 빈 배열과 원소 하나에서는 시작 부모가 음수라 반복이 실행되지 않습니다.

heapify를 각 원소의 삽입으로 구현하면 O(N log N) 상한이 자연스럽지만, 이 아래에서 위로 만드는 과정은 O(N)입니다. 깊게 내려갈 수 있는 높은 정점의 수가 적기 때문입니다. 대략 절반인 잎은 내려가지 않고, 그 위의 약 4분의 1은 한 층 정도만 내려갑니다. 높이별 비용을 합하면 선형 규모가 됩니다.

루트를 끝으로 옮기고 힙 길이를 하나 줄입니다

최대 힙의 루트는 아직 남아 있는 값 중 최댓값입니다. 루트와 현재 힙의 마지막 원소를 바꾸면 그 최댓값의 최종 위치가 확정됩니다. 이제 힙 길이를 하나 줄여 확정한 위치를 제외하고, 새 루트에만 siftDown을 수행합니다. 두 자식 아래는 원래의 힙 조건이 유지되므로 배열 전체를 다시 heapify할 필요가 없습니다. 오른쪽 구간은 이미 오름차순으로 확정되어 더는 변경하지 않습니다.

위 배열에서 10을 오른쪽 끝으로 옮기고 앞 네 칸을 고치면 [5,4,3,1 | 10]입니다. 다음에는 5가 확정되어 [4,1,3 | 5,10], 그다음 [3,1 | 4,5,10]이 됩니다. 마지막에는 [1,3,4,5,10]이 됩니다. 경계의 오른쪽 원소까지 siftDown의 비교 대상에 넣으면 확정한 큰 값이 다시 앞으로 올라오므로 size의 의미를 항상 확인해야 합니다.

같은 배열과 일정한 추가 공간을 유지합니다

heapify와 heapSort는 입력 배열의 원소를 직접 바꾸고 같은 배열 객체를 반환합니다. 새 힙에 모든 값을 삽입한 뒤 결과 배열로 꺼내는 방식은 이 글의 제자리 구현과 다릅니다. 반복형 siftDown에서 임시 값과 인덱스만 사용하므로 입력·출력 배열을 제외한 추가 공간은 O(1)입니다. 초기 heapify O(N) 뒤에 최대 N−1번, 한 번당 O(log N)의 하향 조정을 하므로 정렬의 최악 시간은 O(N log N)입니다.

이 구현은 빈칸 없이 채운 유한한 Number 배열을 받습니다. NaN은 크기 비교를 일관되게 할 수 없고 무한대·문자열·빈칸은 정한 계약 밖이므로 원소 교환 전에 거절합니다. 중복 값은 모두 보존하고 오름차순으로 정렬하지만 힙 정렬은 안정 정렬이 아닙니다. 같은 키에 표식이 있는 원소를 생각하면 멀리 떨어진 루트·끝 교환이 동률의 상대 순서를 바꿀 수 있습니다. 기존 순서를 유지해야 하는 레코드 정렬에는 그 요구를 별도로 반영해야 합니다.

전체 코드와 직접 실행

개념을 읽었다면 아래 예제를 직접 실행하며 상태 변화를 확인할 수 있습니다.

function siftDown(array, root, size) {
  while (2*root+1 < size) {
    let child = 2*root+1;
    if (child+1 < size && array[child+1] > array[child]) child++;
    if (array[root] >= array[child]) break;
    const temporary = array[root];
    array[root] = array[child];
    array[child] = temporary;
    root = child;
  }
}

function heapify(array) {
  if (!Array.isArray(array)) throw new TypeError('유한한 수의 배열이 필요합니다.');
  for (let i = 0; i < array.length; i++) {
    if (!Number.isFinite(array[i])) throw new TypeError('빈칸 없이 유한한 수만 넣으세요.');
  }
  for (let parent = Math.floor(array.length/2)-1; parent >= 0; parent--) {
    siftDown(array,parent,array.length);
  }
  return array;
}

function heapSort(array) {
  heapify(array);
  for (let end = array.length-1; end > 0; end--) {
    const temporary = array[0];
    array[0] = array[end];
    array[end] = temporary;
    siftDown(array,0,end);
  }
  return array;
}

const values = [4,10,3,5,1];
console.log(JSON.stringify(heapify(values)));
console.log(JSON.stringify(heapSort(values)));
console.log(JSON.stringify(heapSort([7,1,7,-2,0])));

node algorithm-in-place-heap-sort.mjs

[10,5,3,4,1]
[1,3,4,5,10]
[-2,0,1,7,7]

비용과 적용 범위

유한한 Number가 빈칸 없이 들어 있는 길이 N의 배열을 직접 바꿉니다. 바닥부터 heapify는 O(N), 정렬 최악 시간 O(N log N), 반복형 구현의 추가 공간 O(1)입니다. 같은 배열을 반환하고 중복 값은 보존하지만 안정 정렬은 아닙니다.

직접 확인해 보기

최대 힙 [5,4,3,1]의 첫 정렬 단계 후, 앞 세 칸의 힙과 오른쪽 확정 구간은 무엇일까요? siftDown의 size는 얼마일까요?

함께 읽을 글

• JavaScript 최소 힙 구현: 우선순위 큐의 push·pop과 비교 함수 — 힙의 부모·자식 불변식과 우선순위 큐 연산을 복습합니다.
• JavaScript 배열: 인덱스 조회와 삽입·삭제 비용 — 같은 배열을 바꾼다는 계약과 배열 연산의 비용을 이해합니다.

참고 자료

• Open Data Structures — 11.1.3 Heap-sort — 배열 힙 정렬의 최대 힙 구성, 제자리 정렬, 선형 heapify와 O(N log N) 정렬 원리. Java 구현을 복사하지 않고 독립적인 JavaScript 학습 예제를 작성했습니다.