Ukážme si celú implementáciu haldy. Ak vám nejaké detaily neboli jasné, skúste si prejsť program a pozrieť sa, ako funguje.
class Heap:
def __init__(self):
self.data = []
def push(self, what):
self.data.append(what)
where = len(self.data) - 1
while where > 0:
parent = (where - 1) // 2
if self.data[where] > self.data[parent]:
self.data[where], self.data[parent] = self.data[parent], self.data[where]
where = parent
else:
break
def pop(self):
n = len(self.data)
answer = self.data[0]
self.data[0], self.data[n - 1] = self.data[n - 1], self.data[0]
self.data.pop(-1)
where = 0
while True:
dest = where
if 2 * where + 1 < n - 1 and self.data[2 * where + 1] > self.data[dest]:
dest = 2 * where + 1
if 2 * where + 2 < n - 1 and self.data[2 * where + 2] > self.data[dest]:
dest = 2 * where + 2
if dest != where:
self.data[where], self.data[dest] = self.data[dest], self.data[where]
where = dest
else:
return answer