웹사이트 검색

JavaScript를 통한 바이너리 힙 및 우선 순위 큐


트리를 힙이라고 부른다는 데 모두 동의할 수 있다고 확신합니다. 힙을 사용하면 순서가 아닌 중요도에 따라 정렬되는 보다 지능적인 대기열로 데이터를 구조화할 수 있습니다.

개념

형제 간에 값을 비교하고 구성하는 이진 검색 트리와 달리 힙에서는 부모와 자녀 사이에서만 작업합니다. 이렇게 하면 가장 높은 값에서 가장 낮은 값으로 이동하는지 또는 그 반대로 이동하는지에 대한 두 가지 힙 가능성, 즉 최대 힙최소 힙이 제공됩니다. 단순화를 위해 최대 힙을 최소 힙으로 변환하는 것이 매우 쉽기 때문에 최대 힙에만 집중할 것입니다.

이진 검색 트리와 마찬가지로 이진 힙은 부모에 대해 둘 이하의 자식만 가질 수 있습니다. 또한 모든 새 노드가 왼쪽에서 오른쪽으로 채워질 때까지 한 수준에 추가되기 때문에 항상 균형을 유지하기 때문에 특별합니다.

슬프게도 연결된 목록은 일반적으로 왼쪽 및 오른쪽 자식이 있는 트리로 개념화되지만 여전히 가능하지만 일반적으로 이진 힙에 대한 최상의 접근 방식은 아닙니다.

대부분의 경우 배열로 처리하는 것이 더 나을 것이므로 여기서 다룰 내용입니다. 순서는 다음 레벨로 이동하기 전에 레벨에서 왼쪽에서 오른쪽으로 모든 것이 예상되는 대로입니다.

이런 식으로 우리는 노드의 자식을 찾기 위한 매우 일관된 패턴을 만듭니다. 노드의 모든 왼쪽 자식은 부모로부터 정확히 2n + 1 떨어진 위치에 있으며 n은 부모의 인덱스이고 모든 오른쪽 자식은 2n입니다. + 2.

노드 추가

새 노드를 추가하는 것이 어레이에 푸시하는 것만큼 간단해 보이지만 까다로운 부분은 자체와 최대값 사이에 있는 부모 노드와 비교한 다음 그에 따라 다시 정렬해야 한다는 것입니다.

VisuAlgo.net 덕분에 그래픽/애니메이션

새 항목을 배열의 끝으로 푸시한 후에는 더 큰 값을 \버블업\해야 합니다. 먼저 배열의 끝에서 새 항목을 가져와 인덱스로 분해해야 합니다. 해당 색인의 새 항목입니다.

항목을 추가할 때마다 자식을 찾기 위한 등식의 역순인 (n-1)/2를 사용하여 부모를 찾습니다. 부모가 현재 노드보다 작으면 교체한 다음 다음 현재가 될 인덱스를 저장합니다. 부모가 없을 때까지 계속됩니다.

끝에서 인덱스를 점차 위로 이동하므로 0보다 크면 계속 교체합니다.

class BH {
  constructor() {
    this.values = [];
  }
  add(element) {
    this.values.push(element);
    let index = this.values.length - 1;
    const current = this.values[index];

    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      let parent = this.values[parentIndex];

      if (parent <= current) {
        this.values[parentIndex] = current;
        this.values[index] = parent;
        index = parentIndex;
      } else break;
    }
  }
}

const tree = new BH();
tree.add(3);
tree.add(4);
tree.add(31);
tree.add(6);
console.log(tree); // [31, 6, 4, 3]

최대 제거

최상위 노드를 제거하는 것은 생각보다 조금 더 복잡합니다. 첫 번째 노드인 최대값을 반환한 다음 배열의 끝인 마지막 노드를 가져와 새 최대값으로 설정합니다.

그렇게 하면 가장 낮은 값을 다른 값과 비교하기 위한 쉬운 기준으로 사용할 수 있습니다. 그 과정에서 비교 및 스왑을 수행하는 동안 트리 맨 아래로 다시 \가라앉습니다\.

VisuAlgo.net 덕분에 그래픽/애니메이션

간단한 부분은 현재 최대값을 잡고 마지막 항목으로 바꾸기 전에 팝하는 것입니다. 그런 다음 다른 모든 작업이 완료된 후 원래 최대값을 반환할 수 있습니다.

시작 인덱스가 있으면 오른쪽 및 왼쪽 자식을 모두 가져오려고 합니다. 왼쪽 자식이 유효한 항목이고 더 크면 swap으로 저장하여 모든 비교가 완료되었을 때 교체를 실행할 수 있습니다.

오른쪽 자식은 조금 더 복잡합니다. 우리는 가장 큰 자식 하나만 부모와 교체하기를 원합니다. rightChild가 아직 정의되지 않았거나 leftChild보다 큰 경우에만 swap으로 설정할 수 있다는 별도의 요구 사항을 추가할 것입니다.

class BH {
  extractMax() {
    const max = this.values[0];
    const end = this.values.pop();
    this.values[0] = end;

    let index = 0;
    const length = this.values.length;
    const current = this.values[0];
    while (true) {
      let leftChildIndex = 2 * index + 1;
      let rightChildIndex = 2 * index + 2;
      let leftChild, rightChild;
      let swap = null;

      if (leftChildIndex < length) {
        leftChild = this.values[leftChildIndex];
        if (leftChild > current) swap = leftChildIndex;
      }
      if (rightChildIndex < length) {
        rightChild = this.values[rightChildIndex];
        if (
          (swap === null && rightChild > current) ||
          (swap !== null && rightChild > leftChild)
        )
          swap = rightChildIndex;
      }

      if (swap === null) break;
      this.values[index] = this.values[swap];
      this.values[swap] = current;
      index = swap;
    }

    return max;
  }
}

const tree = new BH();
tree.add(3);
tree.add(4);
tree.add(31);
tree.add(6);
console.log(tree.extractMax()); // 31

우선순위 대기열

약간의 조정을 통해 바이너리 힙을 대기열과 혼합하고 데이터가 추가된 시기가 아니라 중요도에 따라 데이터를 구성하는 대기열 유형을 생성할 수 있습니다.

단일 숫자 대신 노드를 저장하여 간단하게 이를 달성할 수 있습니다. 각 노드에는 순서를 결정하는 데 사용할 우선 순위 수준(1-5라고 가정)이 있습니다. 두 노드의 우선 순위가 같으면 왼쪽 자식이 먼저 추가되었으므로 먼저 이동합니다.

if 문에서 비교할 때마다 노드의 우선 순위를 사용하기만 하면 됩니다.

class Node {
  constructor(val, priority) {
    this.val = val;
    this.priority = priority;
  }
}

class PQ {
  constructor() {
    this.values = [];
  }
  enqueue(val, priority) {
    let newNode = new Node(val, priority);
    this.values.push(newNode);
    let index = this.values.length - 1;
    const current = this.values[index];

    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      let parent = this.values[parentIndex];

      if (parent.priority <= current.priority) {
        this.values[parentIndex] = current;
        this.values[index] = parent;
        index = parentIndex;
      } else break;
    }
  }
  dequeue() {
    const max = this.values[0];
    const end = this.values.pop();
    this.values[0] = end;

    let index = 0;
    const length = this.values.length;
    const current = this.values[0];
    while (true) {
      let leftChildIndex = 2 * index + 1;
      let rightChildIndex = 2 * index + 2;
      let leftChild, rightChild;
      let swap = null;

      if (leftChildIndex < length) {
        leftChild = this.values[leftChildIndex];
        if (leftChild.priority > current.priority) swap = leftChildIndex;
      }
      if (rightChildIndex < length) {
        rightChild = this.values[rightChildIndex];
        if (
          (swap === null && rightChild.priority > current.priority) ||
          (swap !== null && rightChild.priority > leftChild.priority)
        )
          swap = rightChildIndex;
      }

      if (swap === null) break;
      this.values[index] = this.values[swap];
      this.values[swap] = current;
      index = swap;
    }

    return max;
  }
}

const tree = new BH();
tree.enqueue(3, 2);
tree.enqueue(4, 5);
tree.enqueue(31, 1);
tree.enqueue(6, 3);
console.log(tree.dequeue()); // 4
console.log(tree.dequeue()); // 6
console.log(tree.dequeue()); // 3
console.log(tree.dequeue()); // 31

마무리 생각

트리 순회 우선 순위 대기열에 표준 대기열을 사용한 것과 마찬가지로 그래프와 더 복잡한 구조를 지능적으로 순회하는 데 필수적입니다.

최대 힙을 최소 힙으로 변환하는 것은 모든 비교에서 보다 큼을 부호보다 작음으로 변경하는 것만큼 간단합니다.