[알고리즘] 힙 - JavaScript

힙? 

이진 트리 형태를 가지며 우선 순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제 될 때 

바로 정렬되는 특징이 있다. 

힙의 특징

• 우선 순위가 높은 요소가 먼저 나가는 특징이 있다. 
• 루트가 가장 큰 값이 되는 최대 힙과 루트가 가장 작은 값이 되는 최소 힙이 있다. 
• 자바스크립트에선 직접 구현해야지 사용이 가능하다. 

JavaScript에서 사용하기

class MaxHeap {
  constructor() {
      this.heap = [null];
  }

  push(value) {
      this.heap.push(value);
      let currentIndex = this.heap.length - 1;
      let parentIndex = Math.floor(currentIndex / 2);

      while (parentIndex !== 0 && this.heap[parentIndex] < value) {
          const temp = this.heap[parentIndex];
          this.heap[parentIndex] = value;
          this.heap[currentIndex] = temp;

          currentIndex = parentIndex;
          parentIndex = Math.floor(currentIndex / 2);
      }
  }

  pop() {
      if (this.heap.length === 2) return this.heap.pop(); 

      const returnValue = this.heap[1];
      this.heap[1] = this.heap.pop();

      let currentIndex  = 1;
      let leftIndex = 2;
      let rightIndex = 3;
      while (this.heap[currentIndex] < this.heap[leftIndex] || 
             this.heap[currentIndex] < this.heap[rightIndex]) {
          if (this.heap[leftIndex] < this.heap[rightIndex]) {
              const temp = this.heap[currentIndex];
              this.heap[currentIndex] = this.heap[rightIndex];
              this.heap[rightIndex] = temp;
              currentIndex = rightIndex;
          } else {
              const temp = this.heap[currentIndex];
              this.heap[currentIndex] = this.heap[leftIndex];
              this.heap[leftIndex] = temp;
              currentIndex = leftIndex;
          }
          leftIndex = currentIndex * 2;
          rightIndex = currentIndex * 2 + 1;
      }

      return returnValue;
  }
}

 

더 알아보기 

힙 정렬에 대해서 더 알고 싶다면 [알고리즘] 힙정렬을 보는 것을 추천한다.