class MinHeap(object): def __init__(self, iterable=()): self.array = [None] self.array.extend(iterable) self.build() def build(self): a, size = self.array, self.size() for i in xrange(size / 2, 0, -1): c = 2 * i while c <= size: if c + 1 <= size and a[c+1] < a[c]: c += 1 if a[c] > a[c/2]: break a[c], a[c/2] = a[c/2], a[c] c *= 2 def insert(self, k): self.array.append(k) a, i = self.array, self.size() while i > 1 and k < a[i/2]: a[i] = a[i/2] i /= 2 a[i] = k def pop(self): size = self.size() if size == 0: raise IndexError('pop from empty heap') a = self.array res = a[1] last = a.pop() size -= 1 if size > 0: c = 2 * 1 while c <= size: if c + 1 <= size and a[c+1] < a[c]: c += 1 if a[c] >= last: break a[c/2] = a[c] c *= 2 a[c/2] = last return res def size(self): return len(self.array) - 1 if __name__ == '__main__': from random import shuffle data = range(50) shuffle(data) PRint data h = MinHeap(data) for _ in xrange(len(data)): print h.pop() |
新闻热点
疑难解答
