Python. Двоичная куча

Начал изучать язык питон. Для практики решил реализовать популярные структуры данных. Сижу уже часа 3 с этим вопросом. Элементы в куче сортируются неверно.Алгоритм взят из книги Кормен и Лейзер.
class BinHeap: def __init__(self): self.heaplist = [0] self.heapsize = 0
def left(self,i): return i*2 + 1
def right(self,i): return i*2 + 2
def heapify(self,i): l = self.left(i) r = self.right(i) if(l <= self.heapsize and self.heaplist[l] < self.heaplist[i]): largest = l else: largest = i if( r <= self.heapsize and self.heaplist[r] < self.heaplist[i]): largest = r if(largest != i): self.heaplist[i], self.heaplist[largest] = self.heaplist[largest], self.heaplist[i] self.heapify(largest)
def buildHeap(self,list): self.heaplist = list self.heapsize = len(list) for i in range(len(list)//2-1): self.heapify(i)
def heapSort(self): pass
def extractMax(self): pass
def getHeap(self): return self.heaplist
heap = BinHeap() heap.buildHeap([9,5,23,2,2,1]) print heap.getHeap()

Ответ

Таки открыл Кормена и самое первое - для удобства(?) в книге индексация начинается с единицы. Из-за этого все индексы необходимо скорректировать - левый, правый, heapsize, последний элемент. И знаки в heapify перепутаны. Сложив все вместе и отметив ваши ошибки комментами:
class BinHeap: def __init__(self): self.heaplist = [] self.heapsize = 0
def left(self, i): return i * 2 + 1
def right(self, i): return i * 2 + 2
def heapify(self, i): l = self.left(i) r = self.right(i) # Знаки if l <= self.heapsize and self.heaplist[l] > self.heaplist[i]: largest = l else: largest = i # Знаки и последний индекс if r <= self.heapsize and self.heaplist[r] > self.heaplist[largest]: largest = r if largest != i: # Обмен значениями явный tmp = self.heaplist[i] self.heaplist[i] = self.heaplist[largest] self.heaplist[largest] = tmp self.heapify(largest)
def buildHeap(self, list): self.heaplist = list # Из-за того, что у вас в процедуре используется <=, heapsize должен быть строго меньше, чтобы избежать выхода за пределы self.heapsize = len(list) - 1 # Индексы также c середины и до нуля включительно for i in range(len(list) // 2, -1, -1): print(i) self.heapify(i)
def heapSort(self): pass
def extractMax(self): pass
def getHeap(self): return self.heaplist
heap = BinHeap() heap.buildHeap([0, 0, 9, 5, 23, 0, 0, 2, 2, 1, 4, 0, 12, -1, 0]) print(heap.getHeap())
Результат:
>>> [23, 5, 12, 2, 4, 9, 0, 0, 2, 1, 0, 0, 0, -1, 0]
23 5 12 2 4 9 0 0 2 1 0 0 0 -1 0
Требование, чтобы каждый потомок был меньше либо равно родителя выполнено.