[Algorithm] Binary Heap (이진 힙)

binaryHeap

• 이진 힙은 트리 객체를 이용해 구현할 수도 있고, 배열로도 구현할 수 있다.

• 완전 이진 트리는 노드가 낮은 레벨부터 채워지고, 같은 레벨에서는 왼쪽부터 채워지기 때문에 배열로 구현하는 것이 쉽다.

• 최대 힙과 이진 검색 트리(binary search tree)는 둘다 완전 이진 트리

  이진 검색 트리에서는 모든 노드가 정렬

  최대 힙에서는 오직 부모 노드와 직계 자식들 간의 관계만 유지

• 이진 검색 트리 → 오른쪽 자식 노드의 값 >부모 노드의 값

• 최대 힙 → 부모 노드의 값이 > 두 자식 노드의 값

힙은 최대 혹은 최소 값을 삭제할 때 사용한다. 힙은 최대/최소값에 접근하는데 O(1) 시간이 소비된다. 힙은 우선순위 큐를 구현하는데 사용된다.

최대힙 구하기

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

//parent node i left node  = 2i *1 right node = 2i *2
//search parentIdx
function getParentIdx(idx) {
  // search parentIdx
}
// currentIdx 들어오는 heap의 가장 마지막 index
// currentIdx의 parentIdx 찾기 
// reduce가 끝날 때 까지 반복 while 
// swap이 일어나는 조건 생각해보기 
// 값을 바꿔줬으면 인덱스값도 바꿔주자 
function insert(heap, item) {
  heap.push(item);
  // currentIdx 들어오는 heap의 가장 마지막 index
// currentIdx의 parentIdx 찾기 
// reduce가 끝날 때 까지 반복 while 
// swap이 일어나는 조건 생각해보기 
// 값을 바꿔줬으면 인덱스값도 바꿔주자 
  return heap;
}

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