Я создаю класс 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)
x.insert (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]
Как бы я сделал его?