[자료구조] 힙 Heap 자바스크립트(Javascript)로 구현하기

힙 Heap 이란? 

최댓값과 최솟값을 찾아내는 연산을 빠르게 수행하고자 고안된 이진트리 기반 데이터 구조이다. 

삽입과 삭제 시 O(log n)의 시간복잡도를 가진다.

최대 힙 Max Heap

상위 노드에 제일 큰 값이 위치한다. 

위의 트리구조 힙을 배열로 나타내면 아래와 같다.

 

부모 노드 인덱스 & 자식 노드 인덱스 구하기

• 부모 노드 인덱스 : 자식 노드 인덱스 / 2
• 왼쪽 자식 노드 인덱스 : 부모 노드 인덱스 * 2 + 1
• 오른쪽 자식 노드 인덱스 : 부모 노드 인덱스 * 2 + 2

 

삽입

기존의 최소 힙에 새로운 값 17을 삽입한다고 해보자.

→ 코드 상에서 add(17)에 해당

위와 같이 마지막 노드의 왼쪽부터 삽입할 노드를 추가한다. 그 후 부모 노드와 크기를 비교하며 정렬해나간다. 
→ 코드 상에서 heapifyUp에 해당

최대 힙에서 노드 꺼내기 ( 삭제 )

→ 코드 상에서 remove에 해당

최대 힙을 사용하는 이유는 최댓값을 찾아내기 위함이다. 따라서 최대 힙에서 노드를 꺼낼 경우 최상위 노드를 꺼내주면 된다.

이렇게 최상위 노드를 꺼내게 되면 최상위 노드의 자리가 빈 상태가 된다.

이때 트리의 맨 마지막 노드를 최상위 노드 자리로 옮긴다. 

 

그 후 정렬이 되지 않은 상태이기 때문에 최상위 노드는 자식 노드와 값을 비교해 정렬을 수행한다.

이 정렬을 해나가는 과정이 코드의 heapifyDown에 해당한다.

 

최대 힙 자바스크립트 코드

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

  getParentIndex(idx) {
    return Math.floor((idx - 1) / 2);
  }

  getRightChildIndex(idx) {
    return idx * 2 + 2;
  }

  getLeftChildIndex(idx) {
    return idx * 2 + 1;
  }

  hasParent(idx) {
    return this.getParentIndex(idx) >= 0;
  }

  add(val) {
    this.heap.push(val);
    this.heapifyUp();
  }

  remove() {
    if (this.heap.length === 0) return null;

    const top = this.heap[0];
    this.heap[0] = this.heap[this.heap.length - 1];
    this.heap.pop();
    this.heapifyDown();
    return top;
  }

  heapifyUp(val) {
    let idx = this.heap.length - 1;
    while (this.hasParent(idx)) {
      let parentIdx = getParentIndex(idx);
      if (this.heap[idx] > this.heap[parentIdx]) {
        this.swap(idx, parentIdx);
        idx = parentIdx;
      } else {
        break;
      }
    }
  }

  heapifyDown() {
    let idx = 0;
    while (this.getLeftChildIndex(idx) > 0) {
      let largerIdx = this.getLeftChildIndex(idx);
      if (
        this.getRightChildIndex(idx) < this.heap.length &&
        this.heap[this.getRightChildIndex(idx)] < this.heap[largerIdx]
      ) {
        largerIdx = this.getRightChildIndex(idx);
      }
      if (this.heap[largerIdx] > this.heap[idx]) {
        this.swap(largerIdx, idx);
        idx = largerIdx;
      } else {
        break;
      }
    }
  }

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

 

최소 힙 Min Heap

상위 노드에 제일 작은 값이 위치한다. 

위의 최소 힙을 배열로 나타내면 다음과 같다. 

 

부모 노드 인덱스 & 자식 노드 인덱스 구하기

• 부모 노드 인덱스 : ( 자식 노드 인덱스 - 1 ) / 2
• 왼쪽 자식 노드 인덱스 : 부모 노드 인덱스 * 2 + 1
• 오른쪽 자식 노드 인덱스 : 부모 노드 인덱스 * 2 + 2

삽입

기존의 최소 힙에 새로운 값 1을 삽입한다고 해보자.

→ 코드 상에서 add(1)에 해당

위와 같이 마지막 노드의 왼쪽부터 삽입할 노드를 추가한다. 그 후 부모 노드와 크기를 비교하며 정렬해나간다. 

→ 코드 상에서 heapifyUp에 해당

최소 힙에서 노드 꺼내기 ( 삭제 )

→ 코드 상에서 remove에 해당

최소 힙을 사용하는 이유는 최솟값을 찾아내기 위함이다. 따라서 최소 힙에서 노드를 꺼낼 경우 최상위 노드를 꺼내주면 된다.

이렇게 최상위 노드를 꺼내게 되면 최상위 노드의 자리가 빈 상태가 된다. 

이때 트리의 맨 마지막 노드를 최상위 노드 자리로 옮긴다. 

이 상태는 현재 정렬이 되지 않은 상태이기 때문에 최상위 노드는 자식 노드와 값을 비교해 정렬을 수행한다. 

이 정렬을 해나가는 과정이 코드의 heapifyDown에 해당한다.

 

최소 힙 자바스크립트 코드 

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

  getParentIndex(idx) {
    return Math.floor((idx - 1) / 2);
  }

  getRightChildIndex(idx) {
    return idx * 2 + 2;
  }

  getLeftChildIndex(idx) {
    return idx * 2 + 1;
  }

  hasParent(idx) {
    return this.getParentIndex(idx) >= 0;
  }

  add(val) {
    this.heap.push(val);
    this.heapifyUp();
  }

  remove() {
    if (this.heap.length === 0) return null;

    const top = this.heap[0];
    this.heap[0] = this.heap[this.heap.length - 1];
    this.heap.pop();
    this.heapifyDown();
    return top;
  }

  heapifyUp() {
    let idx = this.heap.length - 1;
    while (this.hasParent(idx)) {
      const parent = this.getParentIndex(idx);
      if (this.heap[parent] > this.heap[idx]) {
        this.swap(parent, idx);
        idx = parent;
      } else {
        break;
      }
    }
  }

  heapifyDown() {
    let idx = 0;
    while (this.getLeftChildIndex(idx) < this.heap.length) {
      let smallerIdx = this.getLeftChildIndex(idx);
      const rightIdx = this.getRightChildIndex(idx);
      if (
        rightIdx < this.heap.length &&
        this.heap[rightIdx] < this.heap[smallerIdx]
      ) {
        smallerIdx = rightIdx;
      }
      if (this.heap[smallerIdx] < this.heap[idx]) {
        this.swap(smallerIdx, idx);
        idx = smallerIdx;
      } else {
        break;
      }
    }
  }

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

 

---

도움이 되셨다면 하트 눌러주세요