目录:
1.堆的概念
2.堆的性质
3.堆定义操作
4.堆的实现
1.堆的概念
1.1 优先队列：Priority Queue
优先队列的出队跟队列一样从队首出队；
但在优先队列内部，数据项的次序却是由“优先级”来确定：
高优先级的数据项排在队首，而低优先级的数据项则排在后面；这样，优先队列的入队操作就比较复杂，需要将数据项根据其优先级尽量挤到队列前方。
1.2 堆
1. 实现优先队列的经典方案是采用堆数据结构，堆能够将优先队列的入队和出队复杂度都保持在O(log n)
2. 堆一般是由数组实现的，逻辑上堆可以被看做一个完全二叉树(除底层元素外是完全充满的，且底层元素是从左到右排列的)。
3. 堆分为最大堆和最小堆，最大堆是指每个根结点的值大于左右孩子的结点值；最小堆则是根结点的值小于左右孩子的值。
大顶堆和小顶堆.jpg
2.堆的性质
1.为了是堆操作能保持在对数水平上，就必须采用二叉树结构；
2.为保持操作始终在对数数量级上，保持平衡，采用“完全二叉树”的结构来近似实现“平衡”
3.完全二叉树，叶子结点最多只出现在最底层和次底层，而且最底层的叶结点都连续集中在最左边，每个内部结点都有两个子结点，最多只有一个结点例外
4.完全二叉树由于其特殊性，可以用非嵌套列表，以简单方式实现：
# 此时在列表0号索引位置，放置一个哨兵，并不加入计算，故下边满足如下关系：
结点下标：p
左子结点：2p
右子结点：2p+1
其父结点下标：p // 2
image.png
3.堆定义操作
BinaryHeap()：创建一个空二叉堆对象；
insert(k)：将新key加入到堆中；
findMin()：返回堆中的最小项，最小项仍保留在堆中；
delMin()：返回堆中的最小项，同时从堆中删除；
isEmpty()：返回堆是否为空；
size()：返回堆中key的个数；
buildHeap(list)：从一个key列表创建新堆
4.堆的实现
class BinHeap:
def __init__(self):
self.heapList = [0]
self.currentSize = 0
def perUp(self,i):
while i // 2 > 0:
if self.heapList[i] < self.heapList[i // 2]:
self.heapList[i] , self.heapList[i // 2] = self.heapList[i // 2] , self.heapList[i]
i = i // 2
def insert(self,k):
self.heapList.append(k)
self.currentSize = self.currentSize + 1
self.perUp(self.currentSize)
def minChild(self,i):
if i*2 + 1 > self.currentSize:
return i * 2
else:
if self.heapList[i * 2] < self.heapList[i * 2 + 1]:
return i * 2
else:
return i * 2 + 1
def percDown(self,i):
while (i*2) <= self.currentSize:
mc = self.minChild(i)
if self.heapList[i] > self.heapList[mc]:
self.heapList[i] , self.heapList[mc] = self.heapList[mc] , self.heapList[i]
i = mc
def delMin(self):
retval = self.heapList[1]
self.heapList[1] = self.heapList[self.currentSize]
self.currentSize = self.currentSize - 1
self.heapList.pop()
self.percDown(1)
return retval
def buildHeap(self,alist):
i = len(alist) // 2
self.currentSize = len(alist)
self.heapList = [0] + alist[:]
# print(len(self.heapList),i)
while (i > 0):
# print(self.heapList,i)
self.percDown(i)
i = i - 1
print(self.heapList,i)
if __name__ == '__main__':
bh = BinHeap()
bh.buildHeap([100,43,79,0,12])
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
# 运行结果
[0, 0, 12, 79, 43, 100] 0
0
12
43
79
100
