힙 정렬 알고리즘 (Heap Sort Algorithm)

힙 정렬에서는 최소 힙(Min Heap)과 최대 힙(Max Heap) 두 가지 유형의 힙을 사용할 수 있습니다. 다음으로 각각의 힙에 대해 설명해드리겠습니다:

1. 최소 힙(Min Heap): 최소 힙은 부모 노드가 자식 노드보다 작거나 같은 값을 갖는 이진 트리입니다. 이 힙에서는 가장 작은 값이 루트 노드에 위치합니다. 최소 힙을 사용하면 힙에서 가장 작은 값에 빠르게 접근할 수 있습니다.
2. 최대 힙(Max Heap): 최대 힙은 부모 노드가 자식 노드보다 크거나 같은 값을 갖는 이진 트리입니다. 이 힙에서는 가장 큰 값이 루트 노드에 위치합니다. 최대 힙을 사용하면 힙에서 가장 큰 값에 빠르게 접근할 수 있습니다.

힙 정렬에서는 일반적으로 최대 힙을 사용하여 정렬을 수행합니다. 정렬할 배열을 최대 힙으로 구성한 후, 가장 큰 값을 추출하여 정렬된 배열에 넣습니다. 그런 다음 힙의 크기를 줄이고 남은 요소들을 다시 힙 속성을 유지하며 재배치합니다. 이를 통해 배열이 오름차순으로 정렬됩니다.

최소 힙을 사용하는 경우에는 정렬된 배열을 내림차순으로 얻을 수 있습니다. 즉, 가장 작은 값이 루트에 위치하고 이를 추출하여 정렬된 배열에 넣는 방식으로 진행됩니다.

따라서 힙 정렬은 최소 힙과 최대 힙을 사용하여 배열을 정렬하는 유연한 방법이라고 할 수 있습니다.

아래 코드에서 이진트리를 배열로 사용하였습니다. 이는 이진 트리를 배열로 표현하는 것도 가능하기 때문입니다. 배열로 이진 트리를 표현하는 방법 중 가장 일반적인 방법은 "배열 기반 트리" 또는 "인덱스 기반 트리"라고도 알려져 있습니다.

이 방법에서는 각 노드를 배열의 원소로 표현하고, 각 노드의 인덱스를 통해 노드 간의 관계를 나타냅니다. 일반적으로 배열의 인덱스는 0부터 시작하므로, 인덱스 0은 이진 트리의 루트 노드를 나타냅니다. 인덱스 i의 노드의 왼쪽 자식은 인덱스 2i + 1에 위치하고, 오른쪽 자식은 인덱스 2i + 2에 위치합니다.

---

최소 힙 정렬

function minHeapify(array, n, i) {
  let smallest = i; // 현재 노드를 가장 작은 값으로 설정
  const left = 2 * i + 1; // 왼쪽 자식 노드의 인덱스
  const right = 2 * i + 2; // 오른쪽 자식 노드의 인덱스

  // 왼쪽 자식 노드가 현재 노드보다 작으면 smallest를 왼쪽 자식 노드로 갱신
  if (left < n && array[left] < array[smallest]) {
    smallest = left;
  }

  // 오른쪽 자식 노드가 현재 노드보다 작으면 smallest를 오른쪽 자식 노드로 갱신
  if (right < n && array[right] < array[smallest]) {
    smallest = right;
  }

  // 현재 노드가 가장 작은 값이 아니면 해당 위치와 smallest 위치의 값을 교환하고 재귀적으로 minHeapify 호출
  if (smallest !== i) {
    [array[i], array[smallest]] = [array[smallest], array[i]];
    minHeapify(array, n, smallest);
  }
}

function buildMinHeap(array) {
  const n = array.length;

  // 힙 구성
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    minHeapify(array, n, i);
  }
}

function heapSort(array) {
  const n = array.length;

  buildMinHeap(array);

  // 힙 정렬 수행
  for (let i = n - 1; i > 0; i--) {
    // 최소 힙의 루트 노드와 현재 노드를 교환
	if(array[0] > array[i]) {
      [array[0], array[i]] = [array[i], array[0]];
    }
    // 교환된 값을 제외한 나머지 노드들을 최소 힙으로 유지하기 위해 minHeapify 호출
    minHeapify(array, i, 0);
  }

  return array;
}

// 테스트
const arr = [5, 2, 9, 1, 7, 3];
const sortedArr = heapSort(arr);
console.log(sortedArr); // [1, 2, 3, 5, 7, 9]

---

최대 힙 정렬

function maxHeapify(array, n, i) {
  let largest = i; // 현재 노드를 가장 큰 값으로 설정
  const left = 2 * i + 1; // 왼쪽 자식 노드의 인덱스
  const right = 2 * i + 2; // 오른쪽 자식 노드의 인덱스

  // 왼쪽 자식 노드가 현재 노드보다 크면 largest를 왼쪽 자식 노드로 갱신
  if (left < n && array[left] > array[largest]) {
    largest = left;
  }

  // 오른쪽 자식 노드가 현재 노드보다 크면 largest를 오른쪽 자식 노드로 갱신
  if (right < n && array[right] > array[largest]) {
    largest = right;
  }

  // 현재 노드가 가장 큰 값이 아니면 해당 위치와 largest 위치의 값을 교환하고 재귀적으로 maxHeapify 호출
  if (largest !== i) {
    [array[i], array[largest]] = [array[largest], array[i]];
    maxHeapify(array, n, largest);
  }
}

function buildMaxHeap(array) {
  const n = array.length;

  // 힙 구성
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    maxHeapify(array, n, i);
  }
}

function heapSort(array) {
  const n = array.length;

  buildMaxHeap(array);

  // 힙 정렬 수행
  for (let i = n - 1; i > 0; i--) {
    // 최대 힙의 루트 노드와 현재 노드를 교환
    if (array[0] < array[i]) {
      [array[0], array[i]] = [array[i], array[0]];  
    }
    // 교환된 값을 제외한 나머지 노드들을 최대 힙으로 유지하기 위해 maxHeapify 호출
    maxHeapify(array, i, 0);
  }

  return array;
}

// 테스트
const arr = [5, 2, 9, 1, 7, 3];
const sortedArr = heapSort(arr);
console.log(sortedArr); // [1, 2, 3, 5, 7, 9]