[硕.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[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()