查找存储为Ahnentafel数组的二进制最大堆的最小元素

Question

我有一个二进制最大堆(顶部的最大元素),我需要保持它的常量(比如说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).那是对的吗？

Answer 1

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

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