[硕.Love Python] Heap(堆)
class MinHeap(object):def __init__(self, iterable=()):
self.array =
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 < a:
c += 1
if a > a:
break
a, a = a, a
c *= 2
def insert(self, k):
self.array.append(k)
a, i = self.array, self.size()
while i > 1 and k < a:
a = a
i /= 2
a = k
def pop(self):
size = self.size()
if size == 0:
raise IndexError('pop from empty heap')
a = self.array
res = a
last = a.pop()
size -= 1
if size > 0:
c = 2 * 1
while c <= size:
if c + 1 <= size and a < a:
c += 1
if a >= last:
break
a = a
c *= 2
a = 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()
页:
[1]