def parent(self, j):
"""
返回父节点的索引
"""
return (j - 1) // 2
def left(self, j):
"""返回左孩子索引"""
return 2 * j + 1
def right(self, j):
"""返回右孩子索引"""
return 2 * j + 2
def has_left(self, j):
"""通过判断索引是否出了列表来判断是否存在"""
return self.left(j) < len(self.data)
def has_right(self, j):
return self.right(j) < len(self.data)
def swap(self, i, j):
self.data[i], self.data[j] = self.data[j], self.data[i]
def upheap(self, j):
"""向上堆排序"""
parent = self.parent(j)
if j > 0 and self.data[j] < self.data[parent]:
self.swap(j, parent)
self.upheap(parent)
def downheap(self, j):
"""向下堆排序"""
if self.has_left(j):
left = self.left(j)
small = left
if self.has_right(j):
right = self.right(j)
if self.data[right] < self.data[left]:
small = right
if self.data[small] < self.data[j]:
self.swap(small, j)
self.downheap(small)
def __init__(self):
self.data = []
def __len__(self):
return len(self.data)
def add(self, key, value):
"""添加一个元素，并进行向上堆排序"""
self.data.append(self.Item(key, value))
self.upheap(len(self.data) - 1)
def min(self):
if self.is_empty():
raise Empty('Priority queue is empty')
item = self.data[0]
return (item.key, item.value)
def remove_min(self):
if self.is_empty():
raise Empty('Priority queue is empty')
self.swap(0, len(self.data) - 1)
item = self.data.pop()
self.downheap(0)
return (item.key, item.value)
python的heapq模块
Python标准包含了heapq模块，但他并不是一个独立的数据结构，而是提供了一些函数，这些函数吧列表当做堆进行管理,而且元素的优先级就是列表中的元素本身,除此之外它的模型与实现方式与刚才我们自己定义的基本相同
有以下函数：
heappush(L,e): 将元素e存入列表L中并进行堆排序
heappop(L): 取出并返回优先级最小的元素，并重新堆排序
heappushpop(L,e): 将e放入列表中，同时返回最小元素，相当于先执行push，再pop
heap replace(L,e): 与heappushpop类似，是先执行pop，再执行push