在给定密钥处拆分堆

Question

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

堆结构如下：

        8
    9
        5
10
        2
    4
            0
        3
            1

在python中得到[4,3,2,1,0]的好算法是什么，它基本上是10的左子级

父项为（index+1）//2

左边的孩子是2i+1，右边的孩子是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]，所以不是我想要的。我从1开始索引，指向4

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

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)