我有一个二进制最大堆（顶部的最大元素），我需要通过摆脱smallest每次我达到 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)。那是对的吗？
对于任何给定的有效最大堆，最小值仅位于叶节点处。下一个问题是如何在数组中找到堆的叶子节点？如果我们仔细观察数组的最后一个节点，它将是最后一个叶节点。通过公式获取叶子节点的父节点
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
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
