[Algorithm]Sort-Heap Sort

출처 - https://commons.wikimedia.org/wiki/File:Heap_sort_example.gif

Heap Sort은 요소 배열을 정렬하는 데 사용할 수 있는 비교 기반 정렬 알고리즘입니다. 이진 힙을 구성하고 최대(또는 최소) 요소를 반복적으로 추출하여 배열의 끝에 배치함으로써 동작한다. 힙 정렬의 시간 복잡성은 O(n log n)이므로 대규모 데이터 세트에 효율적이다.

Binary Heap

이진 힙은 각 상위 노드의 값이 하위 노드의 값보다 크거나 작은 완전한 이진 트리입니다. 이를 힙 속성이라고 합니다. 이진 힙은 배열로 구현될 수 있는데, 여기서 루트는 인덱스 0에 있고 요소의 자식들은 인덱스 2i + 1과 2i + 2에 있다.

예를 들어, 다음 배열은 이진 최대 힙을 나타냅니다:

[10, 4, 8, 5, 12, 2, 6, 11, 3, 9, 7, 1]

이 힙에서 루트(12)는 하위 노드(11 및 8)보다 크고 각 상위 노드는 하위 노드보다 큽니다.

Heapify

Heapify Operation은 이진 힙의 힙 속성을 유지 관리하는 데 사용됩니다. 이것은 배열과 인덱스 i를 입력으로 하고 i의 자식에 뿌리를 둔 이진 트리가 힙 속성을 만족한다고 가정하지만 i에 뿌리를 둔 이진 트리 자체는 그렇지 않을 수 있다. 그런 다음 인덱스 i에 있는 요소를 트리 아래로 이동하여 힙 속성이 충족될 때까지 더 큰(또는 더 작은) 하위 요소와 스왑합니다.

코드는 아래와 같습니다.

function heapify(arr, n, i) {
  let largest = i;  // Initialize largest as root
  let l = 2 * i + 1;  // left = 2*i + 1
  let r = 2 * i + 2;  // right = 2*i + 2

  // If left child is larger than root
  if (l < n && arr[l] > arr[largest]) {
    largest = l;
  }

  // If right child is larger than largest so far
  if (r < n && arr[r] > arr[largest]) {
    largest = r;
  }

  // If largest is not root
  if (largest !== i) {
    // swap arr[i] and arr[largest]
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    // Recursively heapify the affected sub-tree
    heapify(arr, n, largest);
  }
}

이 함수는 배열 배열, 힙의 크기 및 인덱스 i를 입력으로 사용합니다. 먼저 루트 인덱스 i에 가장 큰 요소를 설정한 다음 인덱스 i에서 노드의 왼쪽 및 오른쪽 하위를 확인하고 필요한 경우 가장 큰 인덱스를 업데이트합니다. 가장 큰 인덱스가 루트 인덱스 i와 같지 않으면 함수는 arr[i]와 arr[ligest]의 값을 스왑하고 영향을 받는 하위 트리에서 힙파이를 재귀적으로 호출합니다.

heap Sort()

힙 정렬 알고리즘은 먼저 요소에서 이진 최대 힙을 구성한 다음 최대 요소를 반복적으로 추출하여 배열의 끝에 배치함으로써 배열을 정렬한다.

코드는 아래와 같습니다.

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

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

  // Extract elements one

결과는 아래와 같습니다.

const arr = [10, 4, 8, 5, 12, 2, 6, 11, 3, 9, 7, 1];
console.log(heapSort(arr)); // Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

먼저 정렬되지 않은 요소 12개로 배열을 정의합니다. 그런 다음 heapSort 함수를 arr에 호출하고 결과를 콘솔에 기록합니다.

출력은 정렬된 배열[1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ,11, 12]입니다.

자바스크립트에서 힙 정렬 알고리즘을 구현했다. 힙 정렬은 시간 복잡도가 O(n log n)인 효율적인 정렬 알고리즘이다. 요소에서 이진 최대 힙을 구성하고 최대 요소를 반복적으로 추출하여 배열의 끝에 배치함으로써 작동합니다.