Возникли проблемы при удалении узла root и использовании максимальной кучи - PullRequest
Новая
       27

Возникли проблемы при удалении узла root и использовании максимальной кучи

1 голос
/ 02 апреля 2020

Я пишу функцию, которая должна удалить узел root из maxheap, представленного списком. У меня проблемы с переупорядочением, чтобы удовлетворить свойство maxheap после удаления узла root. Вот мой код: 

def deleteMax(x):
    x.pop(0)
    curr = self.heap[0]
    rootindex = 0
    leftchild = rootindex*2+1
    rightchild = rootindex*2+2

    while current < x[leftchild] or current < x[rightchild] :
        if current < leftchild :
            x[rootindex ], x[leftchild] = x[leftchild], x[rootindex ]
            rootindex = leftchild
        else:
            x[rootindex ], x[rightchild] = x[rightchild], x[rootindex ]
            rootindex = rightchild

    return x

Пример

x = []

Вставка - это моя функция вставки, которая вставляет значения в правильном порядке. Просто предположите, что я вставляю правильно

вставка (10)

вставка (5)

вставка (14)

вставка (9)

вставка (2)

вставка (11)

вставка (6)

Итак: x = [14, 9, 11, 5, 2, 10, 6] (что правильно)

Но когда я вызываю deleteMax (), он удаляет 14 отлично, но у меня остается:

[9, 11, 5, 2, 10, 6]

Когда я хочу, чтобы это было так, чтобы удовлетворить свойство maxheap и сделать его таким:

[11, 9, 10, 5, 2, 6]

Ответы [ 2 ]

0 голосов
/ 02 апреля 2020

Алгоритм удаления root из максимальной кучи: 

Move the last node in the heap to the root position.
Reduce the heap count by 1.
Set current to the root node.
while current is smaller than either of its children
    swap current with the largest child
    set current to index of the child you swapped it with

Обновление

Ваш обновленный код почти верен, но он не гарантирует, что вы выберете самый большой ребенок. Например, если у вас есть это: 

        1
      5   7

Вы бы поменялись 1 с 5. Вам нужно убедиться, что вы получите наибольшее из детей. Итак: 

current = 0
while (true)
    leftchild = current*2+1
    rightchild = current*2+2
    largest = current

    if (current >= size)
        break;
    if (x[current] < x[leftchild])
        largest = leftchild
    if (rightchild < size && x[largest] < x[rightchild])
        largest = rightchild
    if (largest == current)
        break
    swap(x[current], x[largest])
    current = largest

Приведенный выше код гарантирует, что вы всегда выбираете самое большое из двух дочерних элементов, а также гарантирует, что вы случайно не проверите правильного дочернего элемента, которого там нет.

0 голосов
/ 02 апреля 2020

Ваш алгоритм не совсем верен. Взгляните на анимацию на этой странице: https://www.tutorialspoint.com/data_structures_algorithms/heap_data_structure.htm

Теперь вы начинаете с последнего элемента, а затем перемещаете его вверх. Вместо этого вам нужно взять этот последний элемент, поместить его сверху (там, где раньше находился элемент, который вы только что извлекли), а затем переместить его вниз.

Если мы просто удалим первый элемент массива, то Куча разрывается, потому что все строки смещены, а родительские / дочерние ссылки смещены, поэтому вам нужно что-то положить обратно в это место.

...