通过JavaScript的二进制堆和优先级队列

迷南。 2022-11-27 04:26 108阅读 0赞

While I’m sure we can all agree that [queues][] are the coolest things since sliced bread, we can actually do much better by mixing them with a variation of [trees][] called heaps. With heaps we can structure our data into a more intelligent queue that’s sorted by importance rather than order.

尽管我可以肯定大家都同意， [队列][queues]是切成薄片以来最酷的东西，但实际上，通过将它们与称为堆的[树][trees]混合在一起，可以做得更好。 使用堆，我们可以将数据结构化为更智能的队列，该队列按重要性而不是顺序进行排序。

## 概念 **(**Concepts**)** ##

Unlike with [binary search trees][], where we compared and organized our values across siblings, with heaps we only work between parents and their children. This gives us two possibilities for heaps, the `max heap` and the `min heap`, for whether you’re moving from the highest to the lowest values or vice versa. For simplicity’s sake, we’re only going to focus on the max heap, since it’s so easy to convert it to a min heap.

与[二叉搜索树][binary search trees]不同，在[二叉搜索树中][binary search trees] ，我们在同级兄弟之间比较和组织了我们的价值，而在堆中，我们仅在父母和子女之间工作。 无论是从最高值到最低值，还是从最高值到最低值，这都为堆提供了两种可能性，即`max heap`和`min heap` 。 为简单起见，我们仅关注最大堆，因为将其转换为最小堆非常容易。

Like with binary search trees, binary heaps are only allowed to have two or fewer children to a parent. They are also special since they are always balanced because every new node will be added to a level from left to right until full.

与二叉搜索树一样，二叉堆只允许有两个或更少的子代为父代。 它们也很特别，因为它们始终保持平衡，因为每个新节点都将从左到右添加到一个级别，直到满为止。

Sadly, [linked-lists][] generally aren’t the best approach for binary heaps, despite being usually conceptualized as a tree with left and right children, although it’s still possible.

遗憾的是，尽管[链表][linked-lists]通常被概念化为带有左右两个子节点的树，但它仍然不是二进制堆的最佳方法，尽管仍然可行。

Most of the time it’s going to be better to handle it as an array, so that’s what we’re going to cover here. The order is as you’d expect with everything left to right on a level before moving to the next level.

在大多数情况下，将其作为数组处理会更好，所以这就是我们将要介绍的内容。 顺序是您所期望的，将所有内容从左到右依次移到下一级别。

This way, we create a very consistent pattern for finding a node’s children. All of a node’s left children will be exactly at a position `2n + 1` away from their parent, with `n` being their parent’s index, and all right children being `2n + 2`.

这样，我们创建了一个非常一致的模式来查找节点的子代。 节点的所有左子节点将恰好位于距离其父节点`2n + 1`的位置，其中`n`是其父节点的索引，而所有右子节点将是`2n + 2` 。

## 添加节点 **(**Add Node**)** ##

It would seem like adding a new node would be as simple as pushing onto our array, but the tricky part is that we need to compare it with the parents in between itself and the max, then re-order them accordingly.

似乎添加一个新节点就像将其推入数组一样简单，但棘手的部分是我们需要将其与自身和最大值之间的父级进行比较，然后对其进行重新排序。

Graphic/Animation thanks to [VisuAlgo.net][]

图形/动画得益于[VisuAlgo.net][]

After we push our new item onto the end of the array we’ll need to “bubble up” our larger values. First, we need to grab the new item at the end of the array, which we’ll break into the index and the new item at that index.

在将新项目推送到数组的末尾之后，我们需要“冒泡”更大的值。 首先，我们需要在数组末尾抓取新项，将其分为索引和该索引处的新项。

Every time we add an item we’re going to use the reverse of our equation for finding children, `(n-1)/2`, to find its parent. If its parent is less than the current node, swap them then save its index which will be the next `current`. This will continue until there are no parents left.

每次添加项目时，我们都会使用方程式的逆来查找子项`(n-1)/2` ，以找到其父项。 如果其父节点小于当前节点，则交换它们，然后保存其索引，该索引将成为下一个`current`节点。 这将一直持续到没有父母离开为止。

Since it will gradually be moving our `index` up from the end, as long as it’s greater than zero, keep swapping.

由于它将逐渐使`index`从末尾开始向上移动，只要它大于零，就继续交换。

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]

## 移除最大 **(**Remove Max**)** ##

Removing the topmost node is a bit more complicated than you would think. We’re going to return the first node, our max, then take the last node, the end of our array, and set that as the new max.

删除最顶层的节点比您想象的要复杂一些。 我们将返回第一个节点，即max，然后取最后一个节点，即数组的末尾，并将其设置为新的max。

We do that so we can use our lowest value as an easy baseline to compare with our other values as we “sink down” back to the bottom of the tree while making our comparisons and swaps along the way.

这样做是为了在我们进行比较和交换的同时“沉入”到树的底部时，可以将最低值用作简单的基准与其他值进行比较。

Graphic/Animation thanks to [VisuAlgo.net][]

图形/动画得益于[VisuAlgo.net][]

The simple part is grabbing our current max value and popping it off before replacing it with the last item, then we can return our original max value after everything else is done.

简单的部分是获取我们的当前最大值，然后将其弹出，然后将其替换为最后一项，然后在完成所有其他操作后返回原始的最大值。

Once we have a starting index, we want to grab both its right and left children. If the left child is a valid item and is larger, then we can save it as `swap` to run the swap when all the comparisons are done.

有了起始索引后，我们想抓住它的左右两个孩子。 如果左子项是有效项目且较大，那么我们可以将其另存为`swap`以在完成所有比较后运行swap。

The right child is a bit more complicated, we only want one, and the largest, child to be swapped with the parent. We’ll add a separate requirement that `rightChild` can only be set as `swap` if it hasn’t been defined yet or it’s larger than `leftChild`.

合适的孩子要复杂一点，我们只希望将最大的孩子与父母交换。 我们将添加一个单独的要求，即`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

## 优先队列 **(**Priority Queues**)** ##

With a few minor tweaks we can mix binary heaps with queues and create a type of queue that organizes our data by importance rather than when it was added.

通过一些小的调整，我们可以将二进制堆与队列混合，并创建一种队列类型，该队列按重要性而非添加数据的顺序组织数据。

We can achieve this simply enough by storing nodes instead of single numbers. Each node will have a priority level (let’s say from 1-5), which it will use to determine the order. When the priorities on two nodes are the same, the left child, since it will have been added first, will go first.

我们可以通过存储节点而不是单个数字来简单地实现这一点。 每个节点都有一个优先级(例如1-5)，它将用于确定顺序。 当两个节点上的优先级相同时，左子级将首先添加，因为它将被首先添加。

All we have to do is use the node’s `priority` every time we make a comparison in an `if` statement.

我们要做的就是每次在`if`语句中进行比较时都使用节点的`priority` 。

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

## 总结思想 **(**Closing Thoughts**)** ##

Just like how we used standard queues for [tree traversal][] priority queues will be essential for intelligently traversing graphs and more complicated structures.

就像我们如何将标准队列用于[树遍历][tree traversal]优先级队列一样，对于智能遍历图和更复杂的结构也必不可少。

Converting a max heap to a min heap is as simple as changing our greater than to less than sign in all of our comparisons.

将最大堆转换为最小堆就像在所有比较中将“大于”更改为“小于”一样简单。

> 翻译自: [https://www.digitalocean.com/community/tutorials/js-binary-heaps][https_www.digitalocean.com_community_tutorials_js-binary-heaps]

[queues]: https://www.digitalocean.com/community/tutorials/js-stacks-queues
[trees]: https://www.digitalocean.com/community/tutorials/js-trees
[binary search trees]: https://www.digitalocean.com/community/tutorials/js-binary-search-trees
[linked-lists]: https://www.digitalocean.com/community/tutorials/js-linked-lists-overview
[VisuAlgo.net]: https://visualgo.net
[tree traversal]: https://www.digitalocean.com/community/tutorials/js-tree-traversal
[https_www.digitalocean.com_community_tutorials_js-binary-heaps]: https://www.digitalocean.com/community/tutorials/js-binary-heaps