2

我有一个二进制最大堆（顶部的最大元素），我需要通过每次达到 20 个元素时去掉最小的元素来保持它的大小不变（比如 20 个元素）。二叉堆存储在一个数组中，节点 i 的子节点位于 2*i 和 2*i+1（i 从零开始）。在任何时候，堆都有 'n_elements' 元素，介于 0 和 20 之间。例如，数组 [16,14,10,8,7,9,3,2,4] 将是一个有效的最大二进制堆，其中16 人有 14 岁和 10 岁的孩子，14 人有 8 岁和 7 岁的孩子......

要找到最小的元素，似乎一般我必须从 n_elements/2 到 n_elements 遍历数组：最小的元素不一定是数组中的最后一个。

因此，仅使用该数组，似乎任何寻找/删除最小 elt 的尝试至少是 O(n)。那是对的吗？

4

3 回答 3

5

对于任何给定的有效最大堆，最小值将仅在叶节点处。下一个问题是如何在数组中找到堆的叶子节点？如果我们仔细观察数组的最后一个节点，它将是最后一个叶节点。通过公式获取叶节点的父节点

parent node index = (leaf Node Index)/2

从索引开始线性搜索(parent node index +1)到最后一个叶节点索引，获取该范围内的最小值。

FindMinInMaxHeap(Heap heap)
   startIndex = heap->Array[heap->lastIndex/2]
   if startIndex == 0
          return heap->Array[startIndex]
   Minimum = heap->Array[startIndex + 1]
   for count from startIndex+2 to heap->lastIndex
            if(heap->Array[count] < Minimum)
                Minimum := heap->Array[count]
   print Minimum
于 2013-03-10T14:22:28.063 回答
3

我想不出任何方法可以通过O(n)单独使用堆来提高从最大堆中查找和删除最小元素的性能。您可以采取的一种方法是：

如果您自己创建此堆数据结构，则可以保留一个单独的指针，指向数组中最小元素的位置。因此，每当将新元素添加到堆中时，请检查新元素是否更小。如果是，则更新指针等。然后找到最小的元素O(1)。

MBo 在评论中提出了一个很好的观点，即每次删除后如何获取下一个最小元素。每次删除后，您仍然需要执行 O(n) 来找到下一个最小元素。所以删除仍然是O(n). 但是找到最小的元素将是O(1)

如果您还需要更快地删除，您还需要维护所有元素的最小堆。在这种情况下，删除将是O(log(n)). 插入将花费 2 倍时间，因为您必须插入两个堆，并且它也将占用 2 倍空间。

顺便说一句，如果你在任何时候都只有 20 个元素，这并不重要（除非这是一个家庭作业问题，或者你只是为了好玩）。仅当您计划将其扩展到数千个值时才真正重要。

于 2012-05-29T20:19:49.343 回答
0

有 minmax 堆数据结构：http://en.wikipedia.org/wiki/Min-max_heap。当然，它的代码相当复杂，但是对于两个独立的堆，我们必须使用大量额外的空间（对于第二个堆，用于维护一对一的映射），并且需要两次完成这项工作。

于 2012-05-30T11:03:44.813 回答