1.二叉堆Binary Heap实现优先队列

• 实现优先级队列的经典方法是使用叫作二叉堆的数据结构。二叉堆的入队操作和出队操作均可达到O(1ogn)。

• 二叉堆的有趣之处在于， 其逻辑结构上象二叉树，却是用非嵌套的列表来实现的！

• 最小key排在队首的称为“最小堆minheap” 反之，最大key排在队首的是“ 最大堆max heap

• 堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象

• 堆总是满足下列性质：

• 堆中某个节点的值总是不大于或不小于其父节点的值；

• 堆总是一棵完全二叉树。

• 将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

2.二叉堆操作定义

• ADT BinaryHeap的操作定义如下：

• BinaryHeap()：创建一个空二叉堆对象；

• insert(k)：将新key加入到堆中；

• findMin()：返回堆中的最小项，最小项仍保留在堆中；

• delMin()：返回堆中的最小项，同时从堆中删除；

• isEmpty()：返回堆是否为空；

• size()：返回堆中key的个数；

• buildHeap(list)：从一个key列表创建新堆

3.用非嵌套列表实现二叉堆

• 为了使堆操作能保持在对数水平上，就必须采用二叉树结构；

• 同样，如果要使操作始终保持在对数数量级上，就必须始终保持二叉树的“平衡”

树根左右子树拥有相同数量的节点

• 我们采用“完全二叉树” 的结构来近似实现“平衡”

完全二叉树，叶节点最多只出现在最底层和次底层，而且最底层的叶节点都连续集中在最左边， 每个内部节点都有两个子节点，最多可有1个节点例外

• 完全二叉树由于其特殊性，可以用非嵌套列表，以简单的方式实现，具有很好性质

• 如果节点的下标为p，那么其左子节点下标为2p，

• 右子节点为2p+1，其父节点下标为p//2

4.堆次序Heap Order

• 任何一个节点x，其父节点p中的key均小于x中的key

• 这样，符合“ 堆” 性质的二叉树，其中任何一条路径，均是一个已排序数列， 根节点的key最小

4.二叉堆的Python实现

1. 二叉堆初始化

采用一个列表来保存堆数据，其中表首下标为0的项无用，但为了后面代码可以用到简单的整数乘除法，仍保留它。

2. insert(key)方法

• 新key加在列表末尾，显然无法保持“ 堆” 次序虽然对其它路径的次序没有影响，但对于其到根的路径可能破坏次序

• 需要将新key沿着路径来“ 上浮” 到其正确位置

注意：新key的“ 上浮” 不会影响其它路径节点的“ 堆” 次序

3. delMin()方法

• 移走整个堆中最小的key:根节点heapList[1] 为了保持“ 完全二叉树” 的性质，只用最后一个节点来代替根节点是不行的

• 同样，这么简单的替换，还是破坏了“ 堆” 次序解决方法：将新的根节点沿着一条路径“ 下沉” ，直到比两个子节点都小

• 下沉” 路径的选择：如果比子节点大，那么选择较小的子节点交换下沉

4. buildHeap(lst)方法：从无序表生成“堆”

• 我们最自然的想法是：用insert(key)方法，将无序表中的数据项逐个insert到堆中，但这么做的总代价是O(nlog n)

• 其实，用“ 下沉” 法，能够将总代价控制在O(n)

代码：

class BinHeap:

def init (self):

self.heapList = [0]

self.currentSize = 0

def percUp(self,i):

while i//2>0:

if self.heapList[i] < self .heapList[i//2] :

tmp = self.heapList[i // 2] #与父节点交换

self.heapList[i// 2] = self.heapList[i]

self.heapList[i] = tmp

i =i//2 #沿路径向上

def insert(self,k):

self.heapList.append(k) #添加到末尾

self.currentSize = self.currentSize + 1

self.percUp( self . currentSize )

def percDown(self,i):

while (i * 2) <= self . currentSize:

mc = self . minChild(i)

if self . heapList[i] > self. heapList[mc]:# 交换下沉

tmp = self . heapList[i]

self.heapList[i] = self. heapList[mc]

self .heapList[mc] = tmp

现在能在网上找到很多很多的学习资源，有免费的也有收费的，当我拿到1套比较全的学习资源之前，我并没着急去看第1节，我而是去审视这套资源是否值得学习，有时候也会去问一些学长的意见，如果可以之后，我会对这套学习资源做1个学习计划，我的学习计划主要包括规划图和学习进度表。

分享给大家这份我薅到的免费视频资料，质量还不错，大家可以跟着学习