这种逻辑可能吗？（关注点：二进制最小堆、优先级队列、insert位于索引0，但根位于索引1）

Question

然而，在我的作业中，教授希望我们将新值插入索引0，然后应用heapify-down将其移动到相应的位置，但根索引仍然应该在索引1。

当从索引1(extractMin)中删除项并且必须对项进行移动以维护优先级队列和二进制min堆结构时，还将使用heapify-down方法的代码。在本例中，索引0处没有项...所有值都位于索引>=1处。

对于在这些情况下使用的heapify-down方法，是否可能保持O（log n）的效率？我应该创建2个heapify down方法吗？目前，我的方法大约有30行代码，在试图修复它以满足赋值要求时，我的代码几乎有100+行代码，其中包含大量的if/else语句。

Answer 1

让您明白extractmin()可以以传统方式实现，我将重点介绍如何实现自顶向下的add(elt)方法。

保证O（log n）性能的一个关键方面是使堆数组紧凑，以便具有n元素并使用索引1作为根的堆始终包含存储在位置1到n中的元素。通常，这是通过在索引n+1处添加一个新元素来实现的，然后对其进行渗透，直到堆属性恢复。要做到自上而下，我们要考虑从上到下而不是从下到上过渡相同的路径。无论哪种方式，顶点集都是相同的，并且可以通过对目标顶点索引n连续减半来确定。使用您选择的默认使用Python权限的名称，下面的简单函数生成给定参数n的索引集：

def index_path(n):
    bits = n.bit_length()
    return [n >> (bits - i) for i in range(1, bits)]

例如，运行index_path(42)生成[1,2,5,10,21]，您可以很容易地确认这是自底向上方法中计算的同一组索引。只要我们坚持通过堆的这条路径，我们就会保持紧凑性。

则该算法为

• 将新元素置于数组的索引0处
• 更新n，堆中的元素数
• 生成从顶部（1）开始但不包括最后一个索引的索引集(n)
• 遍历索引集
  • 如果当前迭代的值≤0^第个值，则前进到下一个；
  • 否则，将第0^个值与当前迭代的值交换

  Python中的快速实现：

  class MyHeap:
      def __init__(self):
          self.ary = [None]
          self.size = 0
  
      def add(self, elt):
          self.ary[0] = elt
          self.size += 1
          for index in index_path(self.size):
              if self.ary[0] < self.ary[index]:
                  self.ary[0], self.ary[index] = self.ary[index], self.ary[0]
          if len(self.ary) > self.size:
              self.ary[self.size] = self.ary[0]
          else:
              self.ary.append(self.ary[0])
          self.inspect()
  
      def inspect(self):
          print(self.ary, self.size)
  

  test_data = [42, 42, 96, 17, 1, 3, 5, 29, 12, 39]
  test_heap = MyHeap()
  test_heap.inspect()
  for x in test_data:   
      test_heap.add(x)
  

  [None] 0
  [42, 42] 1
  [42, 42, 42] 2
  [96, 42, 42, 96] 3
  [42, 17, 42, 96, 42] 4
  [42, 1, 17, 96, 42, 42] 5
  [96, 1, 17, 3, 42, 42, 96] 6
  [5, 1, 17, 3, 42, 42, 96, 5] 7
  [42, 1, 17, 3, 29, 42, 96, 5, 42] 8
  [29, 1, 12, 3, 17, 42, 96, 5, 42, 29] 9
  [42, 1, 12, 3, 17, 39, 96, 5, 42, 29, 42] 10