0

作为免责声明，我是该网站的新手，因此不太了解如何提问。请不要太苛刻，因为我真的只是想了解其中一些概念是如何工作的。如果我在开始时缺少理解，请告诉我，这样我就可以从那里开始，而不会浪费你的时间。这里什么都没有。因为我认为我的理解可能存在缺陷，所以我提出了一些关于堆如何在不同领域发挥作用的问题，然后尝试回答这些问题。

首先，我想帮助了解添加到空堆中的一组随机数字的外观。例如，我有 9、4、5、3、2、7、8、7。将其添加到堆后，堆会是什么样子？我可以直观地理解这一点（我认为）9 是根，4 是第一个左孩子等等，但由于这不是专门的树，而是一个堆，它会通过切换对数字进行排序吗它们（见“如果我的理解是正确的”段落），以便它们按最小或最大顺序排序？

现在假设我们从堆中删除了 9（我相信 9 将是根），我们将如何应对这种变化，然后将什么放入根中？我认为如果 9 是根节点，我们将取下一个最大的数字并将其复制到 9 的插槽中，而如果这是一个最小堆并且我们只是在底部删除一个节点，它只会被删除 no问题。

沿着类似的思路，获取数组中堆项的父项的公式是什么？--我想我明白这一点，如果父母在i，左孩子将在i * 2，右孩子将在i * 2 + 1。因此要找到父代，我们必须除以 i/2 才能找到父代。例如，如果我们在 i=7 处，父级将是 i=3，因为 3.5 将被截断，如果我们在 i=6 处，父级也将是 i=3。在这个例子中，i = 7 处的孩子将是 i = 3 的右孩子，而 i=6 将是 i = 3 的左孩子。

如果我对此的理解是正确的，那么在将新术语添加到根后进行重新整理，我会将孩子与父母进行比较，如果孩子更大，请切换术语。但是我需要比较两个孩子（如果有两个），看看哪个更大，然后决定哪个孩子需要交换。这将是一个最大堆，而另一个方向是最小堆。

最后，如果我在哪里添加根元素，它将如何重新堆积？

4

2 回答 2

0

删除 9 后，没有任何东西成为根。heapsort 算法去左孩子进行排序（你说 4。）然后是右孩子（或 5）等等。如果检查的数字是根（我们有不同的实现）那么 4 成为根，然后 5等等。如果你感到困惑，看看这个堆排序的定义，用javascript写的：

var heapSort = function(array) {
  var swap = function(array, firstIndex, secondIndex) {
    var temp = array[firstIndex];
    array[firstIndex] = array[secondIndex];
    array[secondIndex] = temp;
  };
  var maxHeap = function(array, i) {
    var l = 2 * i;
    var r = l + 1;
    var largest;
    if (l < array.heapSize && array[l] > array[i]) {
      largest = l;
    } else {
      largest = i;
    }
    if (r < array.heapSize && array[r] > array[largest]) {
      largest = r;
    }
    if (largest !== i) {
      swap(array, i, largest);
      maxHeap(array, largest);
    }
  };
  var buildHeap = function(array) {
    array.heapSize = array.length;
    for (var i = Math.floor(array.length / 2); i >= 0; i--) {
      maxHeap(array, i);
    }
  };
  buildHeap(array);
  for (var i = array.length-1; i >= 1; i--) {
    swap(array, 0, i);
    array.heapSize--;
    maxHeap(array, 0);
  }
  array.heapMaximum = function(){
      return this[0];
  };
  array.heapExtractMax = function(){
      if(this.heapSize < 1){
          throw new RangeError("heap underflow");
      }
      var max = this[0];
      this[0] = this[this.heapSize - 1];
      this.heapSize--;
      maxHeap(this, 1);
      return max;
  };
  array.heapIncreaseKey = function(i, key){
      if(key < this[i]){
          throw new SyntaxError("new key is smaller than current key");
      }
      this[i] = key;
      while(i > 1 && this[Math.floor(i / 2)] < this[i]){
          swap(this, i, Math.floor(i / 2));
          i = Math.floor(i / 2);
      }
  };
  array.maxHeapInsert = function(key){
      this.heapSize--;
      this[this.heapSize] = -Infinity;
      this.heapIncreaseKey(this.heapSize, key);
  };
};
var a = [Math.floor(Math.random() * 100), Math.floor(Math.random() * 100), Math.floor(Math.random() * 100), Math.floor(Math.random() * 100), Math.floor(Math.random() * 100)];
heapSort(a);
document.writeln(a);
*{
  font-family:monospace;
}

我实际上不知道它会如何重新堆积，但是您可以查看该片段以找出答案。

于 2015-03-28T00:33:13.603 回答
0

首先是关于堆外观的第一个问题。它将采用完全二叉树的结构。我们可以沿着列表向下走并更新我们看到的树，但这会破坏运行时间，所以有一个更聪明的方法来做到这一点。我们首先要线性地遍历数组并将其添加到最左边的空槽，其中数组中的第一个条目是根。然后，一旦你有了一个数组，我们就想从头开始修复堆。这涉及查看堆的最高深度并通过交换来修复它，以便最小值是父级。然后在树的深度向上移动一个，如果任何一个孩子小于新的父母，则进行交换。如果这是真的，那么进行交换，但是我们可能已经破坏了 min 属性，因此我们必须递归地向下移动堆以修复该属性。一旦我们递归地移动到顶部并将堆固定在顶部，那么我们将获得所需的最小堆。请注意，通过一些不错的代数，我们可以证明这将在 O(n) 时间内运行。

关于删除 9 的第二个问题是不正确的（因为它不再是根）所以让我们专注于删除根节点。当根节点被删除（从树或数组的第一个条目）时，我们需要为树结构放置一些东西，我们放置树的最左边的节点或数组中的最后一个元素，但是当你可能在想，这可能破坏了 min-property，你是对的。因此，一旦将最左边的节点移至根节点，我们就必须检查它的子节点，如果它比两者都小，那么我们就很好了。否则，我们需要与较小的交换并为下一组孩子重复此操作，直到它比它的两个孩子都小。

在数组中，我们使用 2i 和 2i+1 作为索引是正确的，因此仅除以 2 是不够的。我们注意到 2i 是偶数，而 2i+1 是奇数，所以我们应该关注我们正在查看的索引是偶数还是奇数。但是，截断会为父母提供正确的答案，并且小数会导致左右孩子的决定是正确的。

为了解决您的最后一个问题，我们应该注意，当您将某些内容添加到堆时，它是一棵完整的二叉树，应该添加到最左边的槽而不是根。当你向最左边添加一些东西时（对于一个最小堆），我们需要检查它是否小于它的父母并将它移向根。

此外，当需要运行 prim 算法或 Dijkstra 最短路径算法时，使用 O(n) 构建堆非常有效。

希望这会有所帮助 - 杰森

于 2020-04-05T00:50:45.087 回答