Возникли проблемы при удовлетворении свойства maxheap с использованием списка - PullRequest
0 голосов
/ 02 апреля 2020

Я создаю класс MaxHeap, и я должен сделать это, используя список. У меня возникают проблемы при вставке элемента в кучу в правильном порядке для удовлетворения требования maxheap. Мне не разрешено добавлять что-либо в конструктор. Что мне делать?

class MaxHeap:  

    def __init__(self):
        self.Heap=[]

    def parent(self, pos): 
        return pos//2


    def leftChild(self, pos): 
        return 2 * pos 


    def rightChild(self, pos): 
        return (2 * pos) + 1

    def insert(self, element):
        self.Heap.append(element)
        child = len(self.Heap) - 1

        while child > 0:
            parent = self.parent(child)
            if self.Heap[parent] >= self.Heap[child]:
                return

            self.Heap[child], self.Heap[parent] = self.Heap[parent], self.Heap[child]
            child = parent

Что делает мой код (слева) и что ожидается (справа) (разделено |)

x = MaxHeap ()

x.insert (10)

  • [10] | [10]

x.insert (5)

  • [10,5] | [10,5]

x.insert (14)

  • [14,10,5] | [14,5,10] -> на первом месте все идет не так

x.insert (9)

  • [14,10,5,9] | [14,9,10,5] мой код снова неверен и для остальных

x.insert (2)

  • [14,10,5,9,2] | [14,9,10,5,2]

x.insert (11)

  • [14,11,10,9, 2,5] | [14,9,11,5,2,10]

x.insert (6)

  • [14,11,10, 9,2,5,6] | [14,9,11,5,2,10,6]

При вставке 14 это изначально правильный дочерний элемент 10. Затем вы меняете местами 14 и 10, и обход уровня heap - представление массива, 14 - родитель, 5 - левый и 10 - правый дочерний элемент и т. д. c.

Когда я первоначально добавляю 14, он переходит от [10,5] к [10,5 , 14]

Используя [10,5,14], я сравниваю 14 с его родителем, который был бы 10. Это не удовлетворяет свойству максимальной кучи, поэтому мне нужно переключить 10 с 14, так что оно становится [14,5,10]

Как бы я сделал его?

1 Ответ

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

Python списки индексируются, начиная с 0, но используемые вами родительские / дочерние формулы предназначены для кучи с корнем в 1.

Для кучи с корнем в 0:

leftChild(x) = x*2+1
rightChild(x) = x*2+2
parent(x) = (x-1)//2
...