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