힙 정렬(Heap Sort)의 미니 구현 방법 자바스크립트

개요

힙 정렬은 컴퓨터 과학에서 중요한 정렬 알고리즘 중 하나입니다. 자바스크립트로 이를 간단하게 구현할 수 있는 방법을 설명하겠습니다. 본 문서는 특히 자바스크립트로 ‘미니 힙 정렬’을 구현하는 데 초점을 맞추고 있습니다.

힙 정렬이란?

힙 정렬은 이진 힙(binary heap) 자료구조를 사용하여 배열을 정렬하는 알고리즘입니다. ‘이진 힙’이란 부모 노드와 그에 속한 자식 노드간의 관계를 통해 배열된 트리구조를 말합니다.

코드의 에러: ‘ReferenceError’

문제의 코드에서 ReferenceError라는 에러가 발생하는 경우가 있습니다. 이 에러는 변수나 함수를 정의하지 않았지만 사용하려고 할 때 일어납니다.

미니 힙 정렬 구현하기

1단계: 힙 생성

배열을 이진 힙으로 변환하려면 ‘힙화(Heapify)’라는 과정을 거쳐야 합니다. 힙화는 주어진 배열에서 가장 큰(또는 가장 작은) 요소를 힙의 루트로 만들고, 나머지 요소들도 힙의 조건에 맞게 재배열하는 작업입니다.

function heapify(arr, n, i) {
  let largest = i;
  let left = 2 * i + 1;
  let right = 2 * i + 2;

  if (left < n && arr[left] > arr[largest]) {
    largest = left;
  }

  if (right < n && arr[right] > arr[largest]) {
    largest = right;
  }

  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, n, largest);
  }
}

2단계: 힙 정렬 실행

힙을 생성한 후, 배열의 마지막 요소와 힙의 루트를 교환하고 힙 크기를 줄입니다. 이 과정을 반복하면 배열이 정렬됩니다.

function heapSort(arr) {
  let n = arr.length;

  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }

  for (let i = n - 1; i >= 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapify(arr, i, 0);
  }
}

결론

자바스크립트를 사용하여 힙 정렬을 구현하는 것은 복잡하지 않습니다. 힙화와 배열 요소의 교환만 잘 이해한다면, 간단한 코드로 효율적인 정렬이 가능합니다. 이 기법은 다양한 데이터 정렬에 활용될 수 있으므로 알고 있으면 매우 유용합니다.