本文共 951 字，大约阅读时间需要 3 分钟。
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()
转载地址：https://blog.csdn.net/weixin_39926014/article/details/111025136 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
发表评论
最新留言
关于作者
