Как поменять новое добавленное число в правильную позицию в двоичной куче? - PullRequest
Новая
       33

Как поменять новое добавленное число в правильную позицию в двоичной куче?

0 голосов
/ 26 мая 2019

Этот вопрос моей домашней работы прошел список, где индекс 1 - это новый узел, а также корень. Затем я должен проверить, меньше ли он детей, чем он сам, и поменять его местами с меньшим ребенком. Я написал некоторый код, но он не работает. 

def perc_down(data):
    count = 0
    index = 1
    l, r = 2 * index, 2 * index + 1
    while index < len(data):
        if data[index] > data[l] and data[index] > data[r]:
            min_i = data.index(min(data[l], data[r]))
            data[index], data[min_i] = data[min_i], data[index]
            count += 1
            index = min_i
    return count

values = [0, 100, 7, 8, 9, 22, 45, 12, 16, 27, 36]
swaps = perc_down(values)
print('Binary heap =',values)# should be [0, 7, 9, 8, 16, 22, 45, 12, 100, 27, 36]
print('Swaps =', swaps)# should be 3

1 Ответ

2 голосов
/ 26 мая 2019

Дайте значения l и r внутри цикла while 

while index <= len(data) // 2:
    l, r = 2 * index, 2 * index + 1
    if r >= len(data):
        r = index
    if data[index] > data[l] or data[index] > data[r]:
        min_i = data.index(min(data[l], data[r]))
        data[index], data[min_i] = data[min_i], data[index]
        count += 1
        index = min_i
    print(data) #Added this for easy debugging. 
return count

И запустить цикл до половины значений только потому, что это двоичная минимальная куча.
Выход: 

[0, 7, 100, 8, 9, 22, 45, 12, 16, 27, 36]
[0, 7, 9, 8, 100, 22, 45, 12, 16, 27, 36]
[0, 7, 9, 8, 16, 22, 45, 12, 100, 27, 36]
Binary heap = [0, 7, 9, 8, 16, 22, 45, 12, 100, 27, 36]
Swaps = 3

Пересмотрен алгоритм для тех индексов, чьи дети не существуют.
Для: values = [0, 100, 7, 11, 9, 8, 45, 12, 16, 27, 36] для 100 после двух перестановок с индексом 5, у которого нет правого потомка, поэтому, когда он превышает длину списка, мы просто возвращаем его к исходному индексу.
Heapified список: Binary heap = [0, 7, 8, 11, 9, 36, 45, 12, 16, 27, 100].

...