1. ADT模型

• 对象：一个有限的有序集

• 操作：
• 初始化
• 插入
• 删除最小的元素
• 寻找最小的元素

2. 简单的实现

• 数组：
• 插入元素到末尾Θ(1)
• 找到最大/最小元素 Θ(n), 删除元素移动数组Θ(n)

• 链表：
• 插入元素到链表开头Θ(1)
• 找到最大/最小元素 Θ(n), 删除元素 Θ(1)

• 有序数组：
• 插入 找到合适的位置Θ(n) , 移动数组并插入元素Θ(n)
• 删除开头/末尾元素 Θ(1)

• 有序链表：
• 插入 找到合适的位置 Θ(n) , 插入元素Θ(1)
• 删除开头/末尾元素Θ(1)

3. 二叉堆

1. 结构性质：

1. 角标的位置

2. 基本操作：

• 插入(insertion)
• 先放到最后一个位置之后然后和父节点进行比较，不满足条件则和父节点进行交换，直到满足条件
• 对于新的节点，唯一可以放的位置就是下一个空闲位置，否则堆将不再是完全树，但这样可能破坏堆的序，我们一般采用上浮的策略。
• 没有采用交换的操作，速度更快，时间复杂度是

• 删除最小元（delete)
• 我们一般采用下滤的策略。删除最小元后，在根节点产生一个空穴。同时堆少了一个元素，我们必须把堆最后一个元素 X 移动到堆的某个地方。从根节点的空穴开始我们将空穴的两个儿子中的较小者移入空穴，这样就把空穴往下推了一层。重复步骤直到 X 可以放入空穴。
• 将最后一个叶节点放到根节点，然后和两个儿子比较，不满足则和最大（或最小）的儿子交换，直到满足

其他的堆操作¶

需要注意的是，对于小根堆，找除了最小元以外的元素都需要线性搜索整个堆。
• DecreaseKeyDecreaseKey(P,Δ,H) 操作降低在位置 P 处的关键字的值。我们需要上滤操作对堆进行调整。
 
• IncreaseKeyIncreaseKey(P,Δ,H) 操作增加在位置 P 处的关键字的值。我们需要下滤操作对堆进行调整。
 
• DeleteDelete(P,H) 操作删除堆中位置 P 上的节点。这个操作首先执行 DecreaseKey(P,∞,H) 再执行 DeleteMin 即可。
 
• BuildHeapBuildHeap(H) 操作把 N 个关键字作为输出并把它们放在空队中，可以使用 N 个相继的 Insert 操作完成。也可以将 N 个关键字以任意顺序放入树中构成一棵完全二叉树，从倒数第二层开始依次 percolate down. 可以证明这时只需要线性的时间复杂度就可以完成树的构建。
定理：包含 个节点，高度为 ℎ 的理想二叉树，其节点的高度和为 2ℎ+1−1−(ℎ+1)

d-Heaps¶

d-堆是二叉堆的推广，所有的节点都有 d 个儿子（因此二叉堆是 2-堆） d-堆比二叉堆浅，因此 Insert 操作改进为  但对于大的 d, DeleteMin 会花费更多时间，因为我们每层都要找出 d 个儿子中的最小者。这样操作的用时就是 。而且当 d 不是 2 的幂次时，找出儿子和父亲会花费更多的时间。
一些重要的术语：

Priority queue	优先队列
Binary heap	二叉堆
heap order	堆序
percolate up	上浮
percolate down	下滤

需要注意的点⚠️

• full binary tree & complete binary tree
• 每一个节点都完全拥有所有可能的节点node
• 没有missing element 从最开始到最后一个节点
• 如果中间出现blank那么就不是complete tree
• 去掉最后一层之后是一个full binary tree

• 实现的方法

• 可以进行的操作
• insert
• delete_min(dequeue)

• 更先进的优先队列实现的方法

1. 建立一个二叉堆
1. 最底层是从左到右进行实现的
2. 这样的树叫做完全二叉树

2. 因为二叉树比较常规，因此可以使用数组进行实现
1. 任何一个元素i，它的左子树的节点值在2i,它的右子树的节点值在(2i+1)
2. 它的父节点在(int)(i/2)上

3. 最大的heap size 需要提前确定，然后从位置1开始存放节点

4. heap order property 子树如果是一个堆的话，那么它的根节点的值大于（小于）这棵树的其他根节点
1. 特别的对于最小堆来说，最小的根节点所对应的值存放在根节点中

• 堆的声明：

• 初始化创建一个堆

• insert 操作
• 如果x可以放入一个洞中并且并没有违反heap order，那么我们可以完成这项
• 否则我们采用交换父节点的操作，直到correct location被正确的找到
• 这项技术我们可以称作是 percolate up 直到正确的地址可以被选择到
• 但是我们不会采用一致的创建三个变量进行交换
• 而是采用while循环进行波动的方法来进行交换
• 这同样体现了我们设置sentinel的好处，当插入的一个点需要经过多次浮动然后终止到1时候，我们可以采用sentinel来进行比较，因此需要设置sentinel的点比任何可能插入的数字都要更小

• delete min 操作
• 找到最小的点是很容易的，但是除去这个最小的点确实挺复杂的东西
• 当最小的根节点被删去的时候，有一个洞就在根节点附近被创造出来了
• 主要采用的是 percolate down 的做法，这样之后我们就可以成功删除一个根节点，完成delete min的操作了
• 当堆中有偶数个元素，并且遇到只有一个子节点时，就会出现堆中常见的实现错误。你必须确保不要假设总是有两个孩子，所以这通常涉及一个额外的测试。
• 因此需要特别小心警惕如果只有一个子节点的情况
• 前题是已经假设root根节点已经是一个hole了，因此只需要放心大胆的去研究子节点就可以完成整个操作了