Разделение кучи по заданному ключу

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.

parent равен (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)