二叉堆（大优先）

1. Introduction

A Binary (Max) Heap is a complete binary tree that maintains the Max Heap property.

Binary Heap is one possible data structure to model an efficient Priority Queue (PQ) Abstract Data Type (ADT). In a PQ, each element has a "priority" and an element with higher priority is served before an element with lower priority (ties are either simply resolved arbitrarily or broken with standard First-In First-Out (FIFO) rule as with a normal Queue). Try clicking ExtractMax() for a sample animation on extracting the max value of random Binary Heap above.

To focus the discussion scope, this visualization show a Binary Max Heap of integers where duplicates are allowed. See this for an easy conversion to Binary Min Heap. Generally, any other objects that can be compared can be stored in a Binary Max Heap, e.g., Binary Max Heap of floating points, etc.

1-1. 定义

Complete Binary Tree: Every level in the binary tree, except possibly the last/lowest level, is completely filled, and all vertices in the last level are as far left as possible.

Binary Max Heap property: The parent of each vertex - except the root - contains value greater than (or equal to) the value of that vertex. This is an easier-to-verify definition than the following alternative definition: The value of a vertex - except the leaf/leaves - must be greater than (or equal to) the value of its one (or two) child(ren).

1-2. 优先队 ADT（抽象数据类型）

Priority Queue (PQ) Abstract Data Type (ADT) is similar to normal Queue ADT, but with these two major operations:

1. Enqueue(x): Put a new element (key) x into the PQ (in some order),
2. y = Dequeue(): Return an existing element y that has the highest priority (key) in the PQ and if ties, return any.

Discussion: Some PQ ADT reverts to First-In First-Out (FIFO) behavior of a normal Queue in the event there is a tie of highest priority (key) in the PQ. Does guaranteeing stability on equal highest priority (key) makes PQ ADT harder to implement?

1-3. Stability of Equal Highest Key

1-4. 例子

Imagine: You are an Air Traffic Controller (ATC) working in the control tower T of an airport. You have scheduled aircraft X/Y to land in the next 3/6 minutes, respectively. Both have enough fuel for at least the next 15 minutes and both are just 2 minutes away from your airport. You observe that your airport runway is clear at the moment.

               ✈(Y)
                                ✈(X)
                                                 (T)
                                                <--->
                                                 |||
                                                 |||
                                         ________|||_____________

In case you do not know, aircraft can be instructed to fly in holding pattern near the airport until the designated landing time.

1-5. NUS 课堂独享

You have to attend the live lecture to figure out what happens next...

There will be two options presented to you and you will have to decide:

1. Raise AND wave your hand if you choose option A,
2. Raise your hand but do NOT wave it if you choose option B,

If none of the two options is reasonable for you, simply do nothing.

1-6. 例子 - 继续上页

1-7. 优先队例子

1-8. 潜在答案

1-9. 线性的数据结构来做优先队？

1-10. 答案 - 第一部分

1-11. 答案 - 第二部分

2. 动画 + 最大堆特性复习

Now, let's view the visualisation of a (random) Binary (Max) Heap above. You should see a complete binary tree and all vertices except the root satisfy the Max Heap property (A[parent(i)] ≥ A[i]).

You can Toggle the Visualization Mode between the visually more intuitive complete binary tree form or the underlying compact array based implementation of a Binary (Max) Heap.

Quiz: Based on this Binary (Max) Heap property, where will the largest integer be located?

2-1. 二叉堆的高度是 O(log N)

2-2. 以1为首元素的紧凑数组

A complete binary tree can be stored efficiently as a compact array A as there is no gap between vertices of a complete binary tree/elements of a compact array. To simplify the navigation operations below, we use 1-based array. VisuAlgo displays the index of each vertex as a red label below each vertex. Read those indices in sorted order from 1 to N, then you will see the vertices of the complete binary tree from top to down, left to right. To help you understand this, Toggle the Visualization Mode several times.

This way, we can implement basic binary tree traversal operations with simple index manipulations (with help of bit shift manipulation):

1. parent(i) = i>>1, index i divided by 2 (integer division),
2. left(i) = i<<1, index i multiplied by 2,
3. right(i) = (i<<1)+1, index i multiplied by 2 and added by 1.

Pro tip: Try opening two copies of VisuAlgo on two browser windows. Try to visualize the same Binary Max Heap in two different modes and compare them.

3. 最大二叉堆操作

In this visualization, you can perform several Binary (Max) Heap operations:

1. Create(A) - O(N log N) version (N calls of Insert(v) below)
2. Create(A) - O(N) version
3. Insert(v) in O(log N) — you are allowed to insert duplicates
4. 3 versions of ExtractMax():
   1. Once, in O(log N)
   2. K times, i.e., PartialSort(), in O(K log N), or
   3. N times, i.e., HeapSort(), in O(N log N)
5. UpdateKey(i, newv) in O(log N if i is known)
6. Delete(i) in O(log N if i is known)

There are a few other possible Binary (Max) Heap operations, but currently we do not elaborate them for pedagogical reason in a certain NUS module.

3-1. 那些额外的操作是什么？

4. Insert(v)   //插入v

Insert(v): 当我们在往最大二叉堆插入元素 v 的时候 我们只能插入到最后一个元素 N + 1 来维持一个紧凑的数组 = 完整二叉树特性。然而 最大堆的特性仍然可能没被满足。这时我们从插入点往上去修复最大堆特性（如果需要的话）直到整个堆符合最大堆特性。现在点 Insert(v) 几次来插入几个随机的 v 进去现在显示的最大二叉堆。

这个向上走并且修复最大堆特性的操作没有公认的名字。我们叫它 ShiftUp （上移）但是还有人叫它 BubbleUp 或者 IncreaseKey 操作.

4-1. 为什么这样是正确的？

4-2. 答案

4-3. 时间复杂度分析

Insert(v) 的时间复杂度是 O(log N)。

讨论：你理解这个推论吗？

4-4. 答案

5. ExtractMax()  //提取最大元素一次

ExtractMax(): 提取并删除最大二叉堆中的最大元素（根）的操作需要一个在堆中的元素来替换根，不然最大堆（一个完整的二叉树，在中文中的'林‘）会变成两个断开的子树（中文中两个'木’）。这同样也是这个元素必须是最后一个元素N的原因：维持紧凑数组 = 完整二叉树性质。

因为我们要把最大二叉堆中的一个叶顶点晋升成根顶点，它很可能是会违背最大堆特性。ExtractMax() 这时从根往下比较当前值和它的两个子元素的值（如果必要的话）来修复最大二叉堆特性。现在在当前显示的最大二叉堆中试试 ExtractMax()

这个向下走并修复最大堆特性的操作没有公认的名字。我们叫它 ShiftDown （下移）但是还有人叫它 BubbleDown 或者 Heapify 操作。.

5-1. 为什么和比较大的子项比较？

5-2. 答案

5-3. 时间复杂度分析

ExtractMax() 的时间复杂度是 O(log N)。

讨论：你理解这个推论吗？

5-4. 答案

6. 用二叉堆来实现高效的优先队

Up to here, we have a data structure that can implement the two major operations of Priority Queue (PQ) ADT efficiently:

1. For Enqueue(x), we can use Insert(x) in O(log N) time, and
2. For y = Dequeue(), we can use y = ExtractMax() in O(log N) time.

However, we can do a few more operations with Binary Heap.

7. Create(A) - 两种版本

Create(A): 用含有 N 个逗号分隔的数组 A 从一个空的最大二叉堆开始创建一个合法的最大二叉堆

有两种方法完成创建操作一个简单但是慢 -> O(N log N) 另一个用更复杂的技术但是快 -> O(N).

教你一招：在两个浏览器里面同时打开 VisuAlgo。用最差情况 '已排序例子' 去执行不同版本的 Create(A)，你会看到可怕的差距。

7-1. Create(A) - O(N log N)

Create(A) - O(N log N): 单纯的一个接一个的插入 (用 Insert(v) 操作的意思) 所有 N 个在输入数组中的元素进入到一个本来是空的最大二叉堆中。

分析: 这个操作显然是 O(N log N) 我们用了 O(log N) Insert(v) 操作 N 次. 让我们来研究 ’排好序的例子‘ 它是这个操作中比较复杂的例子之一（现在试试 Hard Case - O(N log N) 我们显示了这个例子 A=[1,2,3,4,5,6,7] -- 请耐心等待 这个例子会比较耗时). 如果我们用递增的顺序往一个空的最大二叉堆中插入，每一次插入都会触发一次从插入点（新叶元素）到根的上移操作。

7-2. Create(A) - O(N)

Create(A) - O(N): 更快的版本 Create(A) 操作是 Robert W. Floyd 在 1964年发明的。 它利用了紧凑数组的优势 = 完整的二叉树和所有的叶元素（顶点的一半，见下页）生来就是最大二叉堆。然后这个操作只从最后一个内顶点一路回到根元素来修复最大二叉堆特性（如果必要的话）。

分析: 粗略分析我们得到 O(N/2 log N) = O(N log N) 但是它其实只是 O(2*N) = O(N) — 下面几页会讨论细节。现在试试 Hard Case - O(N) 用相同的输入数组 A=[1,2,3,4,5,6,7] 并且上一页那样观察（不是生成最多次调换的那个）这个版本要比 O(N log N) 版本厉害（快）得多.

7-3. 很多叶元素（叶顶点）

简单证明为什么在最大堆中（里面N个元素）一半的元素都是叶元素（为了概括性，我们假设N是偶数）：

假设最后一个叶元素的序号是 N, 那么它的父元素的序号是 i = N/2 (回忆 这节课). 它的左子元素的序号是 i+1, 如果存在的话 (它其实并不存在), 将会是 2*(i+1) = 2*(N/2+1) = N+2, 这个结果超过了 N (最后一个叶元素) 所以 i+1 一定是一个没有子元素的叶元素。因为二叉堆的序号是连续的，所以序号s [i+1 = N/2+1, i+2 = N/2+2, ..., N], 或者说一半的顶点，都是叶元素。

7-4. 为什么是 O(N)? - 第一部分

7-5. 为什么是 O(N)? - 第二部分

Create(A) 用 O(N) 的版本是这样：

如果以上公式太复杂的话，现代学生会想到用 WolframAlpha 来解决。

8. HeapSort()   //堆排序

堆排序函数HeapSort()： John William Joseph Williams 在1964年发明了堆排序算法和这个二叉堆数据结构. 堆排序的操作 （假定最大二叉堆已经在O(n)的时间复杂度内建立）非常简单。只需要调用提取堆顶函数ExtractMax() n次即可，每次的时间复杂度为O(log N). 现在你可以试一下屏幕上的这个最大二叉堆 HeapSort()

8-1. 讨论

尽管 HeapSort() 在最好/平均/最坏 情况下的时间复杂度都是 θ(N log N) ，它真的是最好的用比较元素的方法来实现的排序算法吗？

讨论点：HeapSort()的缓存性能如何？

8-2. 答案

8-3. PartialSort()

9. 一些额外内容

当你全部学会了的时候，我们邀请你学习更高级的算法，它们用优先队做底层数据结构（之一），例如 Prim's MST algorithm, Dijkstra's SSSP algorithm, A* 搜索算法(还不在 VisuAlgo里), 一些贪婪算法，等等.

9-1. 简单的最大堆 -> 最小堆 转换

9-2. UpdateKey(i, newv)

9-3. Delete(i)

9-4. 答案

9-5. 源代码

如果你在寻找一个最大二叉堆模型来构造优先队，好消息。

C++ 和 Java 已经有内置的优先队实现 它很有可能用的就是这个数据结构。他们是 C++ STL priority_queue (默认的是最大优先队) 和 Java PriorityQueue (默认是最小优先队). 然而这些内置的实现不一定适合我们高效的做一些优先队的扩展操作（因为NUS课程的原因，这里不谈细节）

Python有heapq，但是速度非常慢。OCaml没有内置的优先队列，但是我们可以用另一节课会提到的另一个数据结构来代替。

PS: 堆排序很可能会在 C++ STL 的 partial_sort用到

尽管如此，这里有我们的实现 BinaryHeapDemo.cpp.

9-6. 在线测试

9-7. 在线评审练习

我们还有一些编程问题可以用到二叉堆数据结构UVa 01203 - Argus 和 Kattis - numbertree.

试着解决它们来提高你对这个数据结构的理解。你可以用C++ STL priority_queue, Python heapq或者JAVA PriorityQueue 如果它们可以简化你的解法

9-8. 讨论

9-9. 令人震惊的东西

9-10. 答案