자바스크립트로 힙 구현하기

자바스크립트로 힙 (Heap) 구현하기

• 힙은 최대 힙과 최소 힙으로 구분될 수 있습니다.
• 최대 힙은 모든 부모 노드의 값이 자식 노드의 값보다 큰 힙을 말하고, 최소 힙은 그 반대입니다.
• 힙은 완전이진트리이기 때문에 배열로 쉽게 구현할 수 있습니다.

힙의 시간복잡도

• 삽입: O(logN)
• 삭제: O(logN)

클래스 정의

// 최대 힙
class Heap {
  constructor() {
    this.heap = []; // n:parent, 2*n+1:left child, 2*n+2:right child
  }
}

삽입 메소드 구현

insert(value) {
  this.heap.push(val);
  let cur = this.heap.length-1;
  let parent = Math.floor(cur-1)/2);
  
  // 추가한 값보다 부모 노드의 값이 더 큰 값이 나올 때 까지 root를 향해 Swap해간다.
  while(parent < val) {
    this.swap(this.heap[parent], this.heap[cur]);
    cur = parent;
    parent = Math.floor(cur-1)/2);
  }
}

삭제 메소드 구현

pop() {
  // root 값과 마지막 값을 swap한다.
  const lastIndex = this.heap.length-1;
  this.swap(this.heap[0], this.heap[lastIndex]);
   
  let value = this.heap.pop();
  let cur = 0;
  while(cur < lastIndex) {
    let leftChild = cur*2+1;
    let rightChild = cur*2+2;
    
    // left child가 없다면 해당 노드는 자식 노드가 없다.
    if(leftChild >= lastIndex) {
      break;
    } 
    // left child만 가지고 있을 경우
    else if(rightChild >= lastIndex) {
      // 자식 노드의 값이 더 크다면 swawp한다.
      if(this.heap[cur] < this.heap[leftChild]) {
        this.swap(this.heap[cur], this.heap[rightChild]);
        cur = leftChild;
      }
      else {
        break;
      }
    } 
    // left, right child 모두 가지고 있을 경우
    else {
      // 자식 모두가 자신보다 값이 클 경우 더 큰 값과 swap한다.
      if(this.heap[cur] < this.heap[leftChild] && this.heap[cur] < this.heap[rightChild]) {
        if(this.heap[leftChild] > this.heap[rightChild]) {
          this.swap(this.heap[cur], this.heap[leftChild]);
          cur = leftChild;
        } else {
          this.swap(this.heap[cur], this.heap[rightChild]);
          cur = rightChild;
        }
      } 
      // 어느 한 쪽 자식의 값만 자신의 값보다 더 크다면 그 값과 swap한다.
      else if(this.heap[cur] < this.heap[leftChild]) {
        this.swap(this.heap[cur], this.heap[leftChild]);
        cur = leftChild;
      } else if(this.heap[cur] < this.heap[rightChild]) {
        this.swap(this.heap[cur], this.heap[rightChild]);
        cur = rightChild;
      } else {
        break;
      }
    }
  }
  return value
}

유틸리티 메소드 구현

swap(a, b) {
  [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
}

size() {
  return this.heap.length;
}