二叉堆是可用于实现优先队列的数据结构之一。在优先队列中，每个值都有优先度，优先度高的值排在前面（相等的优先度用与普通队列一样先进先出的顺序打破平局）。试试，一个简单的提取最大值的可视化。
为便于讨论，我们设计了一个不含有重复元素的二叉最大堆，并做成了这个动画。点击这里来观察如何转化成最小堆。
Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
If you are an NUS student and a repeat visitor, please login.
完整二叉树: 每一层都是二叉树 都被填满 ，除了最低/最下面的一层，并且所有的最底层顶点都尽力向左靠拢。
最大二叉堆特性: 每个顶点的父元素 - 除了根元素 - 都比当前元素的值要大。这种定义比下面这种更容易验证：一个顶点的值 - 除了叶顶点 - 必须必它的一个或者两个子元素要大。
Pro-tip 1: Since you are not logged-in, you may be a first time visitor (or not an NUS student) who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown]/[PageUp] to go to the next/previous slide, respectively, (and if the drop-down box is highlighted, you can also use [→ or ↓/← or ↑] to do the same),and [Esc] to toggle between this e-Lecture mode and exploration mode.
优先队 (PQ) 抽象数据结构 (ADT) 和普通的队列 ADT 差不多, 但是它多了以下两个主要操作:
- Enqueue(x): 放一个新元素 (键值) x 进去优先队 (用某种顺序)，
- y = Dequeue(): 返回已经在优先队里的有着最高优先级（键值）的元素 y 如果存在并列情况，返回先入队的那个。也就是说像一个正常的 Queue 那样 先进先出(FIFO)
Pro-tip 2: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2021). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.
想象：你是一个在机场控制塔工作的 空中交通管理员 (ATC)
你已经安排了飞机 X/Y 在接下来的 3/6 分钟分别降落。两辆飞机都有足够飞行15分钟的油并且都在距机场2分钟的位置。据你观察机场跑道现在空旷。
如果你不知道的话，飞机可以听令在机场附近飞 等待航线 直到指定的降落时间。
Pro-tip 3: Other than using the typical media UI at the bottom of the page, you can also control the animation playback using keyboard shortcuts (in Exploration Mode): Spacebar to play/pause/replay the animation, ←/→ to step the animation backwards/forwards, respectively, and -/+ to decrease/increase the animation speed, respectively.
- 举手并且挥手 代表你选择选项A，
- 举手但是不挥手代表你选择选项B，
如果两种选项你都觉得不对，什么也不做就好了。
The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.
If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.
FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.
The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.
If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.
FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.
The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.
If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.
FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.
The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.
If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.
FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.
Quiz: Based on this Binary (Max) Heap property, where will the largest integer be located?
一个完整的二叉树可以被存在一个紧凑数组A中 因为一个完整的数组和一个完整的二叉树一样 中间都没有空隙。为了简化下面的导航操作，我们用以1开始的数组。VisuAlgo 用在每一个顶点下面的 红色标识 来标识顶点的序号。从1 到 N顺序读这些需要，你会看到这个完整二叉树的所有的元素 从上到下，从左到右。为了帮助你更好地理解，几次。
这样，我们可以用操作序号的方式实现简单的二叉树遍历操作（运用简单的 位移操作):- parent(i) = i>>1, 序号 i 除以二 (整数除法),
- left(i) = i<<1, 序号 i 乘 2,
- right(i) = (i<<1)+1, 序号 i 乘 2 再加 1.
在这个动画里，你可以使用以下几种标准的最大二叉堆操作：
- Create(A) - O(N log N) 版本（N 次Insert(v))
- Create(A) - O(N) 版本
- Insert(v) - O(log N) - 允许重复
- 三个版本的ExtractMax()
- 一次，O(log N)
- K次，PartialSort(), O(K log N)
- N次，HeapSort(), O(N log N)
- 一次，O(log N)
- UpdateKey(i, newv), O(log N)，如果i已知
- Delete(i), O(log N)，如果i已知
最大二叉堆还有其他的操作（方法），但是因为NUS的课程标准里面并不包含更多的操作 所以我们暂时不做详细讨论。
The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.
If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.
FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.
Insert(v): 当我们在往最大二叉堆插入元素 v 的时候 我们只能插入到最后一个元素 N + 1 来维持一个紧凑的数组 = 完整二叉树特性。然而 最大堆的特性仍然可能没被满足。这时我们从插入点往上去修复最大堆特性（如果需要的话）直到整个堆符合最大堆特性。现在点 几次来插入几个随机的 v 进去现在显示的最大二叉堆。
这个向上走并且修复最大堆特性的操作没有公认的名字。我们叫它 ShiftUp （上移）但是还有人叫它 BubbleUp 或者 IncreaseKey 操作.
The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.
If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.
FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.
Insert(v) 的时间复杂度是 O(log N)。
讨论：你理解这个推论吗？
The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.
If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.
FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.
ExtractMax(): 提取并删除最大二叉堆中的最大元素（根）的操作需要一个在堆中的元素来替换根，不然最大堆（一个完整的二叉树，在中文中的'林‘）会变成两个断开的子树（中文中两个'木’）。这同样也是这个元素必须是最后一个元素N的原因：维持紧凑数组 = 完整二叉树性质。
因为我们要把最大二叉堆中的一个叶顶点晋升成根顶点，它很可能是会违背最大堆特性。ExtractMax() 这时从根往下比较当前值和它的两个子元素的值（如果必要的话）来修复最大二叉堆特性。现在在当前显示的最大二叉堆中试试
这个向下走并修复最大堆特性的操作没有公认的名字。我们叫它 ShiftDown （下移）但是还有人叫它 BubbleDown 或者 Heapify 操作。.
The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.
If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.
FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.
ExtractMax() 的时间复杂度是 O(log N)。
讨论：你理解这个推论吗？
The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.
If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.
FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.
到这里为止，我们有一个数据结构可以高效实现优先队ADT的两个主要操作：
- Enqueue(x), 可以用 Insert(x) 它花费 O(log N) 的时间
- y = Dequeue(), 可以用 y = ExtractMax() 它花费 O(log N) 的时间.
我们还可以做一些其他的操作。
Create(A): 用含有 N 个逗号分隔的数组 A 从一个空的最大二叉堆开始创建一个合法的最大二叉堆
有两种方法完成创建操作一个简单但是慢 -> O(N log N) 另一个用更复杂的技术但是快 -> O(N).
教你一招：在两个浏览器里面同时打开 VisuAlgo。用最差情况 '已排序例子' 去执行不同版本的 Create(A)，你会看到可怕的差距。
Create(A) - O(N log N): 单纯的一个接一个的插入 (用 Insert(v) 操作的意思) 所有 N 个在输入数组中的元素进入到一个本来是空的最大二叉堆中。
分析: 这个操作显然是 O(N log N) 我们用了 O(log N) Insert(v) 操作 N 次. 让我们来研究 ’排好序的例子‘ 它是这个操作中比较复杂的例子之一（现在试试 我们显示了这个例子 A=[1,2,3,4,5,6,7] -- 请耐心等待 这个例子会比较耗时). 如果我们用递增的顺序往一个空的最大二叉堆中插入，每一次插入都会触发一次从插入点（新叶元素）到根的上移操作。
Create(A) - O(N): 更快的版本 Create(A) 操作是 Robert W. Floyd 在 1964年发明的。 它利用了紧凑数组的优势 = 完整的二叉树和所有的叶元素（顶点的一半，见下页）生来就是最大二叉堆。然后这个操作只从最后一个内顶点一路回到根元素来修复最大二叉堆特性（如果必要的话）。
分析: 粗略分析我们得到 O(N/2 log N) = O(N log N) 但是它其实只是 O(2*N) = O(N) — 下面几页会讨论细节。现在试试 用相同的输入数组 A=[1,2,3,4,5,6,7] 并且上一页那样观察（不是生成最多次调换的那个）这个版本要比 O(N log N) 版本厉害（快）得多.
简单证明为什么在最大堆中（里面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], 或者说一半的顶点，都是叶元素。
堆排序函数HeapSort()： John William Joseph Williams 在1964年发明了堆排序算法和这个二叉堆数据结构. 堆排序的操作 （假定最大二叉堆已经在O(n)的时间复杂度内建立）非常简单。只需要调用提取堆顶函数ExtractMax() n次即可，每次的时间复杂度为O(log N). 现在你可以试一下屏幕上的这个最大二叉堆
分析：堆排序显然是O(N log N) - 一个最优的通过比较来排序的算法
Quiz: In worst case scenario, HeapSort() is asymptotically faster than...
Merge SortInsertion Sort
Bubble Sort
Selection Sort
尽管 HeapSort() 在最好/平均/最坏 情况下的时间复杂度都是 θ(N log N) ，它真的是最好的用比较元素的方法来实现的排序算法吗？
讨论点：HeapSort()的缓存性能如何？
The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.
If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.
FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.
当你全部学会了的时候，我们邀请你学习更高级的算法，它们用优先队做底层数据结构（之一），例如 Prim's MST algorithm, Dijkstra's SSSP algorithm, A* 搜索算法(还不在 VisuAlgo里), 一些贪婪算法，等等.
所以，UpdateKey(i, newv)可以在O(log N)内完成，如果我们已知序号i。
The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.
If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.
FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.
如果你在寻找一个最大二叉堆模型来构造优先队，好消息。
C++ 和 Java 已经有内置的优先队实现 它很有可能用的就是这个数据结构。他们是 C++ STL priority_queue (默认的是最大优先队) 和 Java PriorityQueue (默认是最小优先队). 然而这些内置的实现不一定适合我们高效的做一些优先队的扩展操作（因为NUS课程的原因，这里不谈细节）
Python有heapq，但是速度非常慢。OCaml没有内置的优先队列，但是我们可以用另一节课会提到的另一个数据结构来代替。
PS: 堆排序很可能会在 C++ STL 的 partial_sort用到
尽管如此，这里有我们的实现 BinaryHeapDemo.cpp.
我们还有一些编程问题可以用到二叉堆数据结构UVa 01203 - Argus 和 Kattis - numbertree.
试着解决它们来提高你对这个数据结构的理解。你可以用C++ STL priority_queue, Python heapq或者JAVA PriorityQueue 如果它们可以简化你的解法
The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.
If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.
FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.
The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.
If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.
FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.
You have reached the last slide. Return to 'Exploration Mode' to start exploring!
Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.
-> 紧凑数组模式
创建(A) - O(N log N)
创建(A) - O(N)
插入(v)
提取最大值()
UpdateKey(i, newv)
Delete(i)