자바스크립트로 힙 (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;
}
profile
자바스크립트로 개발하는 새내기입니다.

3개의 댓글

comment-user-thumbnail
2020년 5월 28일

중괄호나 괄호가 빠져있는 코드가 중간중간 있네요.
그리고 swap메소드가 실제로 동작하는건가요? 제가 다음 코드로 swap을 해봤는데 잘 안되네요.. 제 코드에 어떤 문제라도 있을까요?

const data = {
  arr: [1, 2],
  swap(a, b) {
    [a, b] = [b, a];
  },
  f() {
    this.swap(this.arr[1], this.arr[0])
  }
}
console.log(data.arr)
data.f()
console.log(data.arr)
1개의 답글