在给定键处拆分堆

Question

给定一个列表：[10, 4, 9, 3, 2, 5, 8, 1, 0]

堆结构如下：

python 有什么好的算法可以得到 [4,3,2,1,0] 基本上是 10.child 的左边

parent 是 (index+1)//2

左边child是2i+1，右边child是2i+2

L = [10, 4, 9, 3, 2, 5, 8, 1, 0]
index = 1
newheap = []
newheap.append(L[index])
leftc = 2 * index + 1
rightc = 2 * index + 2
while(leftc < len(L)):
    newheap.append(L[leftc])
    if(rightc < len(L)):
        newheap.append(L[rightc])
    leftc = 2 * leftc + 1
    rightc = 2 * rightc + 2

print(newheap)

输出

[4,3,2,1]

但我需要 [4,3,2,1, 0]，所以不是我想要的。我从指向 4 的 1 开始索引。

递归会更好吗？不知道该怎么做。

Answer 1

你可以尝试类似的方法:

L = [10, 4, 9, 3, 2, 5, 8, 1, 0]
index = 0
offset = 1
newheap = []
while index < len(L):
    index += offset
    for i in range(offset):
        if index+i == len(L):
            break
        newheap += [L[index+i]]
    offset = 2 * offset
print(newheap)

在给定键处拆分堆

Splitting a heap at given key

python

heap