JavaScript의 힙

지난 주에 우리는 힙의 기초에 대해 배웠습니다. 이번 주에는 JavaScript에 개념을 적용하는 방법을 배울 것입니다.

소개

힙 데이터 구조는 힙 조건을 만족하는 특수 트리 데이터 구조입니다.

In a max-heap, for any given element, its parent’s value is greater than or equal to its value.
In a min-heap, for any given element, its parent’s value is less than or equal to its value.

힙 데이터 구조는 일반적으로 이진 트리로 구현됩니다. 이번 강의에서는 JavaScript로 min-heap을 구현할 것입니다. 최소 힙은 요소를 추가 및 제거하는 경우에도 데이터 세트의 최소값을 효율적으로 추적합니다.

힙은 최단 경로 찾기(Dijkstra 알고리즘) 또는 데이터 세트를 효율적으로 정렬(힙 정렬)과 같은 복잡한 문제에 대한 솔루션을 가능하게 합니다.

기술 인터뷰에서 제기된 어려운 질문 중 일부를 자신 있게 탐색하는 데 필수적인 도구입니다.

힙의 작업을 이해함으로써 문제 해결 툴킷에 귀중한 추가 기능을 추가하게 될 것입니다.

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

  add(value) {
    this.heap.push(value);
    this.size++;
    this.bubbleUp();
  }

  popMin() {
    if (this.size === 0) {
      return null 
    }
    const min = this.heap[1];
    this.heap[1] = this.heap[this.size];
    this.size--;
    this.heap.pop();
    this.heapify();
    return min;
  }

  bubbleUp() {
    let current = this.size;
    while (current > 1 && this.heap[getParent(current)] > this.heap[current]) {
      this.swap(current, getParent(current));
      current = getParent(current);
    }
  }

  heapify() {
    let current = 1;
    let leftChild = getLeft(current);
    let rightChild = getRight(current);
    // Check that there is something to swap (only need to check the left if both exist)
    while (this.canSwap(current, leftChild, rightChild)){
      // Only compare left & right if they both exist
      if (this.exists(leftChild) && this.exists(rightChild)) {
        // Make sure to swap with the smaller of the two children
        if (this.heap[leftChild] < this.heap[rightChild]) {
          this.swap(current, leftChild);
          current = leftChild;
        } else {
          this.swap(current, rightChild);
          current = rightChild;
        }
      } else {
        // If only one child exist, always swap with the left
        this.swap(current, leftChild);
        current = leftChild;
      }
      leftChild = getLeft(current);
      rightChild = getRight(current);
    }
  }

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

  exists(index) {
    return index <= this.size;
  }

  canSwap(current, leftChild, rightChild) {
    // Check that one of the possible swap conditions exists
    return (
      this.exists(leftChild) && this.heap[current] > this.heap[leftChild]
      || this.exists(rightChild) && this.heap[current] > this.heap[rightChild]
    );
  }
}

const getParent = current => Math.floor((current / 2));
const getLeft = current => current * 2;
const getRight = current => current * 2 + 1;

module.exports = MinHeap;

MinHeap 클래스

MinHeap 클래스는 두 가지 정보를 저장합니다.

An array of elements within the heap.
A count of the elements within the heap.

우리의 삶을 더 쉽게 만들기 위해 우리는 항상 null 값을 가진 배열의 시작 부분에 하나의 요소를 유지할 것입니다. 이렇게 하면 항상 0 대신 인덱스 1에 있는 최소 요소를 참조하고 this.size - 1 대신 this.size에 있는 마지막 요소를 참조하여 코딩을 단순화할 수 있습니다.

const minHeap = new MinHeap();
console.log(minHeap.heap);
// [ null ]
console.log(minHeap.size);
// 0

버블 업

MinHeap은 두 가지 조건을 충족해야 합니다.

The element at index 1 is the minimum value in the entire list.
Every child element in the list must be larger than its parent.

.heap 배열에 요소를 추가할 수 있는 .add() 메서드를 정의해 보겠습니다. 또한 추가 요소를 추가할 때 힙 조건을 유지 관리하는 작업을 수행하는 .bubbleUp()을 정의합니다.

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

  add(value) {
    this.heap.push(value);
    console.log(`.. Adding ${value}`);
    console.log(this.heap); 
    this.size++;
    this.bubbleUp();
  }

  bubbleUp() {
    console.log('Bubble Up');
  }
}
module.exports = MinHeap;

상위 및 하위 요소

지금까지 훌륭한 작품! MinHeap은 내부 힙에 요소를 추가하고 실행 횟수를 유지하며 .bubbleUp()의 시작을 갖습니다.

.bubbleUp()의 논리를 살펴보기 전에 힙이 요소를 추적하는 방법을 살펴보겠습니다. 내부 요소를 저장하기 위해 배열을 사용하지만 모든 상위 요소에 최대 두 개의 하위 요소가 있는 이진 트리에서 모델링합니다.

자식 및 부모 요소는 내부 힙 내의 상대 인덱스에 의해 결정됩니다. 요소의 인덱스에 대해 산술을 수행하여 상위 및 하위 요소(존재하는 경우)에 대한 인덱스를 결정할 수 있습니다.

Parent: (index / 2), rounded down
Left Child: index * 2
Right Child: (index * 2) + 1

이러한 계산은 힙의 효율성에 중요하지만 외울 필요는 없으므로 MinHeap.js에 getParent(), getLeft() 및 getRight()의 세 가지 도우미 함수를 제공했습니다.

이러한 도우미는 인덱스를 유일한 매개 변수로 사용하고 해당하는 부모 또는 자식 인덱스를 반환합니다.

const { MinHeap, getParent, getLeft, getRight } = require('./MinHeap');

// instantiate MinHeap and assign to minHeap
const minHeap = new MinHeap();

// sample content of minHeap
minHeap.heap = [ null, 10, 13, 21, 61, 22, 23, 99 ];

// display content of minHeap
console.log(minHeap.heap);

// display the current value, its parent value, left child value and right child value
// replace null with the correct way to access the values of the parent, left child and right child
const current = 3;
const currentValue = minHeap.heap[current];
console.log(`Current value of ${current} is ${currentValue}`);
console.log(`Parent value of ${currentValue} is ${minHeap.heap[getParent(current)]}`);
console.log(`Left child value of ${currentValue} is ${minHeap.heap[getLeft(current)]}`);
console.log(`Right child value of ${currentValue} is ${minHeap.heap[getRight(current)]}`);