JS Heap 구현

완전 이진 트리의 일종으로 우선순위 큐나 Heap sort에서 사용된다. Heap은 Max Heap과 Min Heap 두 가지 종류가 있다. 힙에서 대소관계는 부모 자식 사이에는 성립하지만, 형제 사이에는 성립하지 않는다. 따라서 완전히 정렬되지 않은 반정렬 상태를 유지하고 있다.

 

1. Max Heap : 가장 큰 값이 루트 노드에 존재한다. 모든 노드는 자식 노드보다 부모 노드가 큰 값을 가진다.

2. Min Heap : 가장 작은 값이 루트 노드에 존재한다. 모든 노드는 자식 노드보다 부모 노드가 작다.

 

두 종류의 Heap을 사용해 최댓값이나 최솟값을 찾아내는 연산을 빠르게 할 때 사용한다. Heap에 값을 삽입할 경우에는 bubbleUp을 사용하고, 삭제하는 경우에는 bubbleDown을 사용한다.

 

bubbleUp : 가장 마지막에 원소를 추가하고 부모 노드와 비교하며(= 힙을 올라가며) 적절한 자리를 찾는다.

bubbleDown : 삭제는 루트 노드를 추출하고 맨 마지막 노드를 루트 노드로 가져온다. 그 후 자식 노드들과 비교하며(=힙을 내려가며) 적절한 자리에 위치한다. 왼쪽과 오른쪽 노드가 모두 있는 경우 Max Heap에서는 더 큰 자식 노드와 Min Heap에서는 더 작은 자식 노드와 자리를 변경한다.

 

힙은 배열을 이용해 구현한다.

 

노드의 위치

- 자신 : n

- 부모 : (n - 1) / 2 소수점 이하는 내림

- 왼쪽 자식 : (n*2) + 1

- 오른쪽 자식 : (n*2) + 2

 

class Heap {
  constructor () {
    this.heap = [];
  }
  
  size() {
    return this.heap.length;
  }
  
  peek() {
    return this.heap[0];
  }
  
  push(val) {
    this.heap[this.size()] = val; // 맨 마지막에 값 추가
    this.bubbleUp();
  }
  
  pop() {
    const root = this.heap[0]; // 반환값 저장
    
    this.heap[0] = this.heap[this.size()-1]; // 맨 마지막 노드 루트로 이동
    this.heap.pop();
    this.bubbleDown();
    
    return root;
  }
  
  bubbleUp() {
    // ...
  }
  
  bubbleDown() {
    // ...
  }
}

bubbleUpMaxHeap() {
  let currentIdx = this.size() - 1;
  let parentIdx = Math.floor((currentIdx-1)/2);
  
  while(this.heap[parentIdx] && this.heap[parentIdx] < this.heap[currentIdx]) {
    // swap
    [this.heap[parentIdx],this.heap[currentIdx]] = [this.heap[currentIdx],this.heap[parentIdx]];
    currentIdx = parentIdx;
    parentIdx = Math.floor((currentIdx-1)/2);
  }
}

bubbleUpMinHeap() {
  let currentIdx = this.size() - 1;
  let parentIdx = Math.floor((currentIdx-1)/2);
  
  while(this.heap[parentIdx] && this.heap[parentIdx] > this.heap[currentIdx]) {
    // swap
    [this.heap[parentIdx],this.heap[currentIdx]] = [this.heap[currentIdx],this.heap[parentIdx]];
    currentIdx = parentIdx;
    parentIdx = Math.floor((currentIdx-1)/2);
  }
}

 

bubbleDownMaxHeap() {
  let currentIdx = 0;
  let leftIdx = currentIdx*2+1;
  let rightIdx = currentIdx*2+2;
  
  // 왼쪽 자식노드가 없다면 오른쪽 자식노드도 없기 때문에 왼쪽 노드의 존재 검사
  while(this.heap[leftIdx] && (this.heap[leftIdx] > this.heap[currentIdx] || 
  this.heap[rightIdx] > this.heap[currentIdx])){
    let biggerIdx = leftIdx;
    
    if(this.heap[rightIdx] && this.heap[rightIdx] > this.heap[biggerIdx]) {
      biggerIdx = rightIdx;
    }
    // swap
    [this.heap[currentIdx],this.heap[biggerIdx]] = [this.heap[biggerIdx],this.heap[currentIdx]];
    currentIdx = biggerIdx;
    leftIdx = currentIdx*2+1;
    rightIdx = currentIdx*2+2;
  }
}

bubbleDownMinHeap() {
  let currentIdx = 0;
  let leftIdx = currentIdx*2+1;
  let rightIdx = currentIdx*2+2;
  
  // 왼쪽 자식노드가 없다면 오른쪽 자식노드도 없기 때문에 왼쪽 노드의 존재 검사
  while(this.heap[leftIdx] && (this.heap[leftIdx] < this.heap[currentIdx] || 
  this.heap[rightIdx] < this.heap[currentIdx])){
    let smallerIdx = leftIdx;
    
    if(this.heap[rightIdx] && this.heap[rightIdx] < this.heap[smallerIdx]) {
      smallerIdx = rightIdx;
    }
    // swap
    [this.heap[currentIdx],this.heap[smallerIdx]] = [this.heap[smallerIdx],this.heap[currentIdx]];
    currentIdx = smallerIdx;
    leftIdx = currentIdx*2+1;
    rightIdx = currentIdx*2+2;
  }
}

 

참고

https://yoongrammer.tistory.com/80

https://chamdom.blog/heap-using-js/

https://haruisshort.tistory.com/293