힙 정렬

• 완전 이진트리 기반
• 부모 트리는 모든 경우에 대해 자식 트리보다 크다
• 최댓값, 최솟값을 구할 때 유용하다.
• 시간 복잡도 O(NlogN)

자식 노드는 각각 i * 2 + 1 , i * 2 + 2 로 접근
부모 노드는 (i - 1) / 2 로 접근
인덱스 0은 루트 노드로 항상 최댓값이 들어 있다.

자바스크립트 코드

function heapify(arr) {
  // 주어진 배열을 heap 성질로 정렬
  if (arr.length <= 1) {
    return;
  }
  for (let i = Math.floor(arr.length / 2); i >= 0; i--) {
    max_heapify(arr, i, arr.length);
  }
}

function max_heapify(arr, i, length) {
  let left = i * 2 + 1;
  let right = i * 2 + 2;
  let parent = i;
  // 부모 노드와 왼, 오 노드의 값을 비교해 가장 큰 값을 부모 노드로 올려줌
  if (left < length && arr[left] > arr[parent]) {
    parent = left;
  }
  if (right < length && arr[right] > arr[parent]) {
    parent = right;
  }
  if (i != parent) {
    swap(arr, i, parent);
    max_heapify(arr, parent, length);
  }
}

function swap(arr, i, j) {
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

heap 삽입

function _insert(arr, data) {
  arr.push(data);
  let i = arr.length - 1;
  while (i > 0) {
    const parent = Math.floor((i - 1) / 2);
    if (arr[parent] > arr[i]) {
      // 추가한 노드 값이 부모 노드의 값보다 작을때 까지 반복
      break;
    }
    // 부모 노드가 더 작으면 위치 변경
    swap(arr, i, parent);
    i = parent;
  }
}

heap 삭제

function _delete(arr) {
  //최댓값이 들어있는 root 노드와 최말단 노드의 자리를 바꿈
  swap(arr, 0, arr.length - 1);
  // 최말단으로 옮겨진 최댓값을 빼낸다. pop()
  const max = arr.pop();
  // root 노드에는 최말단 노드가 있기에 다시 재정렬
  heapify(arr);
  return max;
}

참고한 글

힙 정렬(Heap Sort) // Javascript 코드