这个逻辑可能吗？（关注点：二进制最小堆、优先级队列、在索引 0 处插入但根在索引 1 处）

Question

我有一个二进制最小堆优先级队列的工作代码（具有所需的效率），它使索引 0 保持为空并且根节点位于索引 1（子节点为 2i 和 2i+1）。我将新值插入到堆末尾第一个可用的空 space 处，并应用 heapify-up（如果需要）将其向上移动到其各自的位置。这是教科书上说要做的技术。

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

当从索引 1 (extractMin) 中删除项目时，也将使用 heapify-down 方法的代码，并且必须四处移动项目以维护优先级队列和二进制最小堆结构。在这种情况下，索引 0 处没有项目...所有值都位于索引 >= 1.

在这些情况下使用heapify-down方法是否可以保持O(log n)的效率？我应该创建 2 heapify down 方法吗？目前我的方法有大约 30 行代码，在尝试修复它以满足分配要求时，我的代码将近 100 多行代码，其中包含大量 if/else 语句。

感谢您的帮助！！

更新：与教授交谈，他告诉我他只是希望我们使用堆中的所有索引，这样就不会浪费 space。我应该忽略他之前关于在索引 0 + heapify-down 处插入的电子邮件和作业详细信息，而只是将索引 0 用于交换方法。目前我正在使用一个临时变量，所以交换分 3 个步骤完成，但我正在按照他的说明修改它以在 arr[0] 处使用 space - 现在是 4 个步骤但它满足他的要求:-)

Answer 1

按照您的说法，extractMin() 可以用传统方式实现，我将重点介绍如何实现 top-down add(elt) 方法。

保证 O(log n) 性能的一个关键方面是让堆数组紧凑，这样具有 n 个元素的堆使用索引 1 作为根，这些元素总是存储在位置 1通过 n 包括在内。通常这是通过在索引 n + 1 处添加一个新元素然后向上渗透直到堆属性被恢复来实现的。为此 top-down，我们要考虑传输相同的路径，但从上到下而不是从下到上。无论哪种方式，顶点集都是相同的，并且可以通过目标顶点索引 n 的连续减半来确定。将您选择的名称作为使用 Python 的默认许可，以下简单函数生成给定参数 n:

的索引集

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

例如，运行ning index_path(42) 产生 [1, 2, 5, 10, 21]，您可以轻松确认这是在 bottom-up 方法中评估的同一组指数。只要我们坚持通过堆的这条路径，我们就会保持紧凑性。

算法就是

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

^个

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

在每个阶段都可以很容易地确认它是一个有效的堆。

与 bottom-up 方法不同，此版本不能 short-circuit。每次都要经过整条路径。

这个逻辑可能吗？（关注点：二进制最小堆、优先级队列、在索引 0 处插入但根在索引 1 处）

Is this logic possible? (concerns: binary min heap, priority queue, insert at index 0 but root is at index 1)

algorithm

priority-queue

min-heap

这个逻辑可能吗？ （关注点：二进制最小堆、优先级队列、在索引 0 处插入但根在索引 1 处）

Is this logic possible? (concerns: binary min heap, priority queue, insert at index 0 but root is at index 1)

algorithm

priority-queue

min-heap

这个逻辑可能吗？（关注点：二进制最小堆、优先级队列、在索引 0 处插入但根在索引 1 处）