# http://interactivepython.org/courselib/static/pythonds/Trees/BinaryHeapImplementation.html
# start from index 1, so that for node i
# right child index: 2*i+1
# time complexity: O(logn)
self.h, self.n = [0] + A, len(A)
for i in range(self.n//2, 0, -1):
# time complexity: O(logn)
self.h[1], self.h[self.n] = self.h[self.n], self.h[1]
def _ensureNotEmpty(self):
raise Exception("empty tree")
if self.h[i] > self.h[i//2]:
self.h[i//2], self.h[i] = self.h[i], self.h[i//2]
def _bubbleDown(self, i):
if self.h[i] < self.h[mci]:
self.h[i], self.h[mci] = self.h[mci], self.h[i]
if self.h[i*2] > self.h[i*2+1]: