[硕.Love Python] Heap(堆)

分析家

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 = a[i/2]
　　
            i /= 2
　　

　　
        a = 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()