我有一个二进制最小堆优先级队列的工作代码(具有所需的效率)，该队列将索引 0 保留为空，根节点位于索引 1(子节点为 2i 和 2i+1)。我将新值插入堆末尾第一个可用空白处的堆中，并应用堆化(如果需要)将其移动到各自的位置。这是教科书规定要做的技术。
但是，在我的作业中，教授希望我们将新值插入索引 0，然后应用 heapify-down 将其移动到各自的位置，但根索引仍应位于索引 1 处。
当从索引 1 (extractMin) 中删除项目并且必须移动项目以维护优先级队列和二进制最小堆结构时，也将使用堆下方法的代码。在本例中，索引 0 处没有项目...所有值都位于索引>= 1 处。
在这些情况下，是否可以保持 O(log n) 的效率，以便使用堆化方法？ 我应该创建 2 个堆积方法吗？ 目前我的方法有大约 30 行代码，在尝试修复它以满足赋值要求时，我的代码几乎是 100+ 行代码，其中包含大量的 if/else 语句。
感谢您的帮助！！
更新：与教授交谈，他告诉我他只是希望我们使用堆中的所有索引，这样就不会浪费空间。 我应该忽略他之前关于在索引 0 + 堆积处插入的电子邮件和分配详细信息，而只使用索引 0 作为交换方法。目前我正在使用一个临时变量，因此交换分 3 个步骤完成，但我正在按照他的指示对其进行修改以利用 arr[0] 处的空间 - 现在是 4 个步骤，但它符合他的要求：-)
如果您相信extractMin()可以用传统方式实现，我将重点介绍如何实现自上而下的add(elt)方法。
保证 O(log n) 性能的一个关键方面是使堆数组紧凑，以便包含使用索引 1 作为根的n元素的堆始终将这些元素存储在位置 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 个值与当前迭代的值交换
- 在索引
n处追加或插入(如果适用)第 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
在每个阶段都可以轻松确认为有效的堆。
与自下而上的方法不同，此版本不会短路。 它每次都必须遍历整个路径。