29 binary heap 최대힙

최대힙

function swap(idx1, idx2, arr) {
  [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
}

function getParentIdx(idx) {
  return Math.floor((idx - 1) / 2); //부모인덱스 구하기
}

function insert(heap, item) {
  heap.push(item); //힙 배열에 넣고
  let curIdx = heap.length - 1; //현재 인덱스는 힙배열의 마지막 인덱스
  let pIdx = getParentIdx(curIdx); //현재 인덱스의 부모 인덱스
  while (pIdx >= 0 && heap[curIdx] > heap[pIdx]) { //부모 인덱스가 루트까지 올라갈수 있고, 밑에있는 값이 부모값보다 클동안 작동됨
    swap(curIdx, pIdx, heap); //자식값과 부모값 변경
    curIdx = pIdx; //자식값에 부모값 넣고
    pIdx = getParentIdx(curIdx); //다시 부모인덱스값 가져옴
  }
  return heap; //힙 리턴
}

const binaryHeap = function (arr) {
  return arr.reduce((heap, item) => {
    return insert(heap, item);
  }, []);
};