Algorithm JS - 힙 정렬

let array = require("fs")
  .readFileSync(__dirname + "/input.txt")
  .toString()
  .split("\n")
  .slice(1)
  .join()
  .split(" ")
  .map((i) => Number(i));

function heapSort(arr) {
  for (let i = arr.length - 1; i >= 0; i--) {
    // 최대 힙으로 만듬
    arr = maxHeap(arr, i);
    // 만약 arr[0] > arr[i]일 경우 첫번째 노드와 마지막 노드 스왑 but, 1과 1이 같을 경우 스와핑 x
    if (arr[0] > arr[i]) {
      [arr[i], arr[0]] = [arr[0], arr[i]];
    }
  }
  return arr;
}

function maxHeap(array, lastIdx) {
  const arr = array;
  // 부모 인덱스
  let parentIdx = Math.floor(lastIdx / 2) - 1;
  // 부모 인덱스가 1이 될 때까지 순회(가장 높은 인덱스의 부모 노드 부터 시작)
  while (parentIdx !== -1) {
    // 왼쪽 자식 인덱스와 오른쪽 자식 인덱스 지정
    let leftChildIdx = parentIdx * 2 + 1;
    let rightChildIdx = parentIdx * 2 + 2;
    // 만약 오른쪽 자식 노드가 없을 경우
    if (arr[rightChildIdx] === undefined) {
      // 만약 자식 노드가 부모 노드 보다 클 경우 서로 스왑
      if (arr[leftChildIdx] > arr[parentIdx])
        [arr[leftChildIdx], arr[parentIdx]] = [
          arr[parentIdx],
          arr[leftChildIdx],
        ];
    } else {
      // 만약 오른쪽 자식 노드가 있을 경우 3개의 값을 비교하여 자식 노드가 클 경우 부모 노드와 스왑
      let node = Math.max(
        ...[arr[leftChildIdx], arr[rightChildIdx], arr[parentIdx]]
      );
      if (node !== arr[parentIdx]) {
        const swapNodeIdx = arr.indexOf(node);
        [arr[parentIdx], arr[swapNodeIdx]] = [arr[swapNodeIdx], arr[parentIdx]];
      }
    }
    // 다음 부모 노드 비교를 위해 -1 낮춤
    parentIdx = parentIdx - 1;
  }
  return arr;
}

console.log(heapSort(array));