JavaScript의 힙(3부)

JavaScript에서 힙을 사용하는 방법과 방법에 대한 마지막 소개를 위해 클래스와 함께 객체 지향을 사용하여 "힙화"하는 방법에 대해 자세히 알아보겠습니다.

히피파이 I

우리는 최소 요소를 검색했지만 MinHeap을 혼란에 빠뜨렸습니다. 낙심할 이유가 없습니다. 우리는 이전에 이러한 유형의 문제를 처리했으며 MinHeap의 모양을 되찾을 수 있습니다!

.bubbleUp()과 유사한 역할을 수행하는 .heapify() 메서드를 정의합니다. 단, 지금은 위쪽이 아닌 트리 아래쪽으로 이동합니다. 현재 요소는 왼쪽 자식 또는 두 개의 자식을 가질 수 있지만 오른쪽 자식만 가질 수 있는 부모입니다.

자식에 대해 스와핑이 발생할 수 있으면 true를 반환하고 그렇지 않으면 false를 반환하는 도우미 메서드 .canSwap()을 작성했습니다.

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]
    );
  }

최소 힙 조건을 유지하려면 상위 값이 두 하위 값보다 작아야 합니다. 스왑이 필요한지 확인하기 위해 왼쪽 자식부터 시작하여 먼저 자식이 있는지 확인한 다음 최소 힙 조건이 깨졌는지, 즉 현재 요소가 해당 자식의 값보다 큰 값인지 확인합니다. 왼쪽 자식이 최소 힙 조건을 깨뜨리지 않으면 오른쪽 자식에 대해 동일한 검사가 수행됩니다.

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

  popMin() {
    if (this.size === 0) {
      return null
    }
    console.log(`\n.. Swap ${this.heap[1]} with last element ${this.heap[this.size]}`);
    this.swap(1, this.size);
    const min = this.heap.pop();
    this.size--;
    console.log(`.. Removed ${min} from heap`);
    console.log('..',this.heap);
    return min;
  }

  add(value) {
    console.log(`.. adding ${value}`);
    this.heap.push(value);
    this.size++;
    this.bubbleUp();
    console.log(`added ${value} to heap`, this.heap);
  }

  bubbleUp() {
    let current = this.size;
    while (current > 1 && this.heap[getParent(current)] > this.heap[current]) {
      console.log(`.. swap ${this.heap[current]} with parent ${this.heap[getParent(current)]}`);
      this.swap(current, getParent(current));
      console.log('..', this.heap);
      current = getParent(current);
    }
  }

  heapify() {
    let current = 1;
    let leftChild = getLeft(current);
    let rightChild = getRight(current);

    while (this.canSwap(current, leftChild, rightChild)) {
      leftChild = getLeft(current);
      rightChild = getRight(current);
    }
  }

  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]
    );
  }

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

}

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

module.exports = MinHeap;

히피파이 II

.bubbleUp()에서 우리는 항상 우리의 요소를 그 부모와 비교했습니다. .heapify()에는 잠재적으로 두 가지 옵션이 있습니다. 왼쪽 자식과 오른쪽 자식입니다.

우리는 어느 것을 선택해야 합니까? 우리는 그것을 생각하기 위해 예를 사용할 것입니다. 4개의 요소가 있는 힙이 있다고 상상해 보세요.

console.log(minHeap.heap)
// [null, 21, 36, 58, 42]
minHeap.popMin()
// 21
// [null, 42, 36, 58]
// Should we swap 42 with 36 or 58?

우리는 두 자식 중 작은 자식으로 바꾸고 싶습니다. 그렇지 않으면 힙 상태를 유지하지 않을 것입니다.

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

  popMin() {
    if (this.size === 0) {
      return null
    }
    console.log(`\n.. Swap ${this.heap[1]} with last element ${this.heap[this.size]}`);
    this.swap(1, this.size);
    const min = this.heap.pop();
    this.size--;
    console.log(`.. Removed ${min} from heap`);
    console.log('..',this.heap);
    this.heapify();
    return min;
  }

  add(value) {
    console.log(`.. adding ${value}`);
    this.heap.push(value);
    this.size++;
    this.bubbleUp();
    console.log(`added ${value} to heap`, this.heap);
  }

  bubbleUp() {
    let current = this.size;
    while (current > 1 && this.heap[getParent(current)] > this.heap[current]) {
      console.log(`.. swap ${this.heap[current]} with parent ${this.heap[getParent(current)]}`);
      this.swap(current, getParent(current));
      console.log('..', this.heap);
      current = getParent(current);
    }
  }

  heapify() {
    let current = 1;
    let leftChild = getLeft(current);
    let rightChild = getRight(current);

    while (this.canSwap(current, leftChild, rightChild)) {
      while (this.canSwap(current, leftChild, rightChild)) {
      if (this.exists(leftChild) && this.exists(rightChild)) {
        if (this.heap[leftChild] < this.heap[rightChild]) {
          this.swap(current, leftChild);
          current = leftChild;
        } else {
          this.swap(current, rightChild);
          current = rightChild;
        }        
      } else {
        this.swap(current, leftChild);
        current = leftChild;
      }
      leftChild = getLeft(current);
      rightChild = getRight(current);
    }
      leftChild = getLeft(current);
      rightChild = getRight(current);
    }
  }

  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]
    );
  }

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

}

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

module.exports = MinHeap;

검토

이것은 JavaScript에서 최소 힙을 구현하는 방법이며, 이것은 작은 일이 아닙니다(가장 작은 feat를 효율적으로 추적할 수 있지만).

요약하자면 MinHeap은 내부 Javascript 배열 내에서 인덱스 1의 요소로 최소 요소를 추적합니다.

요소를 추가할 때 .bubbleUp()을 사용하여 새 요소를 부모와 비교하여 힙 조건을 위반하는 경우 교체합니다. 자식은 부모보다 커야 합니다.

최소 요소를 제거할 때 힙의 마지막 요소로 교체합니다. 그런 다음 .heapify()를 사용하여 새 루트를 자식과 비교하고 필요한 경우 더 작은 자식으로 교체합니다.

힙은 힙 상태를 유지하는 데 효율적이기 때문에 유용합니다. 값이 감소하는 요소를 사용하여 힙을 빌드하면 계속해서 힙 조건을 위반하게 됩니다. 얼마나 많은 스왑이 발생합니까?