[Heap 힙] - JavaScript로 heap 구현하기

프로그래머스에서 힙 문제를 JS로 푸는데 JS는 힙을 직접 구현해야 된다는 것을 알게 되었다. 

그래서 개념과 함께 JS로 힙을 구현해 볼 것이다.

 

Heap 힙이란?

힙은 완전 이진 트리 기반의 자료구조이다.

주로 "최댓값"이나 "최솟값"을 빠르게 찾아내기 위해 사용된다. 

여기서 이진 트리란 자식 노드가 2개 이하인 트리를 말한다. 

 

 

힙의 조건

1. 완전 이진 트리

    노드의 수가 2^k-1 ( 포화 이진 트리) 이 되지 않아 맨 아래 레벨을 모두 채울 수 없을 때 왼쪽부터 차례로 채운 것.

2. 힙 특성

    최대 힙 : 모든 노드는 값을 갖고, 자식 노드(들) 값보다 크거나 같다. 우선순위가 가장 큰 원소가 루트에 자리하게 된다.

    최소 힙 : 반대로 부모 노드가 자식 노드보다 작거나 같은 힙

 

자바스크립트는 힙을 "직접" 구현해야 하는데 이때 배열을 사용해 구현한다.

완전 이진 트리 특성상 배열의 인덱스만으로 부모와 자식의 위치를 계산할 수 있기 때문이다.

배열이 A[0]부터 시작된다면 A[k]의 자식은 A[2k+1] 과 A[2k+2] 이다.

완전 이진 트리이기 때문에 중간에 빠지는 노드가 없어서 위와 같이 공식으로 구할 수 있다. 

부모 노드 인덱스는 A[Math.floor((k-1)/2)] 로 구할 수 있다.

 

 

힙의 시간 복잡도

최솟값 탐색, 최댓값 탐색 : O(1)
삽입 : O(logN)
삭제 : O(logN)

 

 

힙이 필요한 이유?

힙은 위의 시간 복잡도에서 살펴봤듯이, 최소, 최대 값을 O(1)의 시간복잡도로 얻기 위해서 사용된다.

배열이나 연결 리스트 같은 자료구조는 최소, 최댓값을 얻기 위해 O(n)이 걸린다.

최소 힙의 경우, 최상위 부모 노드에 최솟값이 담겨있기 때문에 최상위 노드만 조회하면 최솟값을 알아낼 수 있기 때문에 O(1)이 걸린다고 볼 수 있다.

 

 

구현

1. 기본 골격

class Heap {
  constructor() {
    this.heap = []; //힙 데이터를 저장할 빈 배열 초기화
  }

  // 두 노드의 위치를 바꾸는 메서드
  swap(idx1, idx2) {
    [this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]];
  }
}

 

2. 삽입

// 삽입 push 배열 끝에 넣기
  push(value) {
    this.heap.push(value); //맨 끝에 추가
    this.bobbleUp(); //부모와 비교하며 위로 올리기
  }

  bubbleUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      // 부모가 나보다 크면 교체
      if (this.heap[parentIndex] > this.heap[index]){
	      this.swap(index, parentIndex);
      }else{
	      break;
	    }
      index = parentIndex; //위치 교환 후 인덱스 업데이트
    }
  }

 

3. 삭제

// 삭제 pop
  pop() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();

    const root = this.heap[0];
    this.heap[0] = this.heap.pop(); //맨 뒤의 것을 루트로
    this.bubbleDown(); //아래로 내리기
    return root;
  }

  //루트 노드가 빠지면, 마지막 노드가 루트자리를 차지하지만 보통 값이 크기 때문에 최소 힙 규칙을 어기게 된다.
  //그래서 자기 자리를 찾아 아래로 내려가야함.
  bubbleDown() {
    let index = 0;

    while (true) {
      let left = index * 2 + 1;
      let right = index * 2 + 2;
      let min = index; //일단 내가 제일 작다고 가정

      // 왼쪽 자식이 나보다 더 작으면 min 후보 등록
      if (left < this.heap.length && this.heap[left] < this.heap[min]) {
        min = left;
      }
      // 오른쪽 자식이 위 후보 또는 나보다 더 작으면 min 업데이트
      if (right < this.heap.length && this.heap[right] < this.heap[min]) {
        min = right;
      }
      // 내가 가장 작은게 맞다면 내려가지 않음
      if (min === index) break;
      // 내가 가장 작은게 아니라면 위치 바꾸고 인덱스 업데이트
      this.swap(index, min);
      index = min; //바뀐 자식 위치로 가서 다시 검사
    }
  }

 

자바스크립트에는 힙을 직접 구현해야 되는 번거로움이 있지만, 오히려 그 과정을 통해 힙의 구조와 동작 원리를 더 명확하게 이해할 수 있게 되었다.