이진 힙(Binary Heap)

힙(Heap)

힙(Heap)이란 트리 기반 자료구조로 힙 속성을 만족하는 거의 완전한 트리입니다. 힙 속성이란 예를 들어, 최대힙(Max Heap)일 경우 부모 노드는 반드시 자식 노드보다 값이 커야 한다는 법칙입니다. 따라서 최상위 노드는 최대값을 가지게 됩니다. 이러한 힙의 특성으로 힙은 우선순위 큐를 구현하는데 적합한 자료구조입니다.
한 가지 참고사항으로 힙은 부모와 자식 노드간의 관계만이 정의되어 있을 뿐, 형제 또는 사촌 노드 간의 우선순위는 정해진 것이 없습니다.

이진 힙(Binary Heap)

이진 힙은 힙 중에서 가장 널리 쓰이는 형태 중 하나로 이진 트리 형태인 힙입니다. 이진 트리는 각 노드의 자식 노드가 반드시 2개 이하인 트리입니다. 이진 힙은 힙정렬 알고리즘을 위한 자료구조로서 1964년 J. W. J. 윌리엄이 발표하였습니다.

이진 힙은 완전 이진 트리라는 조건을 만족해야 합니다. 완전 이진 트리는 모든 레벨의 노드가 채워져 있어야 하며, 마지막 레벨은 왼쪽부터 차 있어야 합니다.

Binary Heap Insert

class MaxBinaryHeap{
  constructor(){
      this.values = [];
  }
  insert(element){
      this.values.push(element);
      this.bubbleUp();
  }
  bubbleUp(){
    let idx = this.values.length - 1;
    const element = this.values[idx];
    while(idx > 0){
          let parentIdx = Math.floor((idx - 1)/2);
          let parent = this.values[parentIdx];
          if(element <= parent) break;
        this.values[parentIdx] = element;
             this.values[idx] = parent;
             idx = parentIdx;         
          
    }
  }
}

let heap = new MaxBinaryHeap();
heap.insert(41);
heap.insert(39);
heap.insert(33);
heap.insert(18);
heap.insert(27);
heap.insert(12);
heap.insert(55);
## console.log(heap,)