二叉堆(大优先)

1. Introduction

一个(最大)二叉堆是一个具有最大堆特性的完全二叉树。
二叉堆是可用于实现优先队列的数据结构之一。在优先队列中,每个值都有优先度,优先度高的值排在前面(相等的优先度用与普通队列一样先进先出的顺序打破平局)。试试ExtractMax(),一个简单的提取最大值的可视化。
为便于讨论,我们设计了一个不含有重复元素的二叉最堆,并做成了这个动画。点击这里来观察如何转化成最小堆。

1-1. 定义

完整二叉树: 每一层都是二叉树 都被填满 ,除了最低/最下面的一层,并且所有的最底层顶点都尽力向左靠拢。


最大二叉堆特性: 每个顶点的父元素 - 除了根元素 - 都比当前元素的值要大。这种定义比下面这种更容易验证:一个顶点的值 - 除了叶顶点 - 必须必它的一个或者两个子元素要大。

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

[This is a hidden slide]

1-4. 例子

想象:你是一个在机场控制塔工作的 空中交通管理员 (ATC)

你已经安排了飞机 X/Y 在接下来的 3/6 分钟分别降落。两辆飞机都有足够飞行15分钟的油并且都在距机场2分钟的位置。据你观察机场跑道现在空旷。

如果你不知道的话,飞机可以听令在机场附近飞 等待航线 直到指定的降落时间。

1-5. NUS 课堂独享

你要参加NUS的课程才会发现接下来会发生什么...
以下两种选择,你必须要做决定:
  1. 举手并且挥手 代表你选择选项A,
  2. 举手但是不挥手代表你选择选项B,

如果两种选项你都觉得不对,什么也不做就好了。

1-6. 例子 - 继续上页

[This is a hidden slide]

1-7. 优先队例子

除了你刚才看到的几个例子外(NUS课堂独享) 现实生活中还有很多可以用到优先队ADT的地方。
讨论:你能提出一些其他的在生活中能用到优先队的地方吗?

1-8. 潜在答案

[This is a hidden slide]

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

我们可以用数组(头尾相连数组)或者链表来构造优先队ADT(抽象数据结构)但是入列队和出列队会比较慢  O(N
 
讨论:为什么?

1-10. 答案 - 第一部分

[This is a hidden slide]

1-11. 答案 - 第二部分

[This is a hidden slide]

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

现在,我们来看上面的随机的最大二叉堆的动画。你应该看到一个完整的二叉树,除了根的所有顶点满足最大堆特性(A[parent(i)] > A[i] - 记住我们不允许重复的整数)。

你可以在视觉上更直观的完整二叉树形式和底层紧凑数组形式之间Toggle the Visualization Mode

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

At one of the leaf
At the root
Can be anywhere

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

要记住的重要知识点:如果我们有一个含有N个元素的二叉堆,因为我们要把它储存成一个完整的二叉树,所以他的高度不会高过 O(log N)
简单分析:一个满的(不止是完整的)含有N个元素的二叉树的高度 h 总是 N = 2(h+1)-1,所以 h = log2(N+1)-1 ~= log2 N。
看上面的例子 N = 7 = 2(2+1)-1 或者 h = log2(7+1)-1 = 2.
对于有关二叉堆的操作 以上知识点很重要。

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

一个完整的二叉树可以被存在一个紧凑数组A中 因为一个完整的数组和一个完整的二叉树一样 中间都没有空隙。为了简化下面的导航操作,我们用以1开始的数组。VisuAlgo 用在每一个顶点下面的 红色标识 来标识顶点的序号。从1 到 N顺序读这些需要,你会看到这个完整二叉树的所有的元素 从上到下,从左到右。为了帮助你更好地理解,Toggle the Visualization Mode几次。

这样,我们可以用操作序号的方式实现简单的二叉树遍历操作(运用简单的 位移操作):
  1. parent(i) = i>>1, 序号 i 除以二 (整数除法),
  2. left(i) = i<<1, 序号 i 乘 2,
  3. right(i) = (i<<1)+1, 序号 i 乘 2 再加 1.
小窍门:在两个浏览器窗口中分别打开VisuAlgo,并比较最大而叉堆的两种不同模式。

3. 最大二叉堆操作

在这个动画里,你可以使用以下几种标准的最大二叉堆操作:

  1. Create(A) - O(N log N) 版本(NInsert(v))
  2. Create(A) - O(N) 版本
  3. Insert(v) - O(log N) - 允许重复
  4. 三个版本的ExtractMax()
    1. 一次,O(log N)
    2. K次,PartialSort(), O(K log N)
    3. N次,HeapSort(), O(N log N)
  5. UpdateKey(i, newv), O(log N),如果i已知
  6. Delete(i), O(log N),如果i已知

最大二叉堆还有其他的操作(方法),但是因为NUS的课程标准里面并不包含更多的操作 所以我们暂时不做详细讨论。

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

[This is a hidden slide]

4. Insert(v)   //插入v

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


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

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

你明白为什么当你插入的新元素违反了最大堆的特性的时候 从插入点(第N+1个元素)往上(最多上到根元素)走,把当前顶点和它的父顶点换位 永远是正确的方法?

4-2. 答案

[This is a hidden slide]

4-3. 时间复杂度分析

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

讨论:你理解这个推论吗?

4-4. 答案

[This is a hidden slide]

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

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

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

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

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

在向下运动修复最大堆特性的时候,为什么当一个顶点有两个子元素的时候,我们必须检查(甚至交换)它两个子元素中较大的那个?
为什么我们不能只比较左(或者右,如果存在的话)顶点?

5-2. 答案

[This is a hidden slide]

5-3. 时间复杂度分析

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

讨论:你理解这个推论吗?

5-4. 答案

[This is a hidden slide]

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

到这里为止,我们有一个数据结构可以高效实现优先队ADT的两个主要操作:

  1. Enqueue(x), 可以用 Insert(x) 它花费 O(log N) 的时间
  2. y = Dequeue(), 可以用 y = ExtractMax() 它花费 O(log N) 的时间.

我们还可以做一些其他的操作。

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)? - 第一部分

首先,我们回忆含有N个元素的满二叉树的高度是log2 N.
其次,要明白运行shiftDown(i)操作所需要的时间不是最高值O(log N), 而是 O(h),h是在以顶点 i 为跟的从树的高度。
最后,在一个高度为 h 的满二叉树中 有ceil(N/2h+1)个顶点。
在上面这个满二叉树的例子中 N = 7, h = 2。 顶点数量为 ceil(7/20+1) = 4 分别是在h = 0  {44,35,26,17} 。在高度h = 1ceil(7/21+1) = 2 个顶点 分别是: {62,53} 在高度h = 2  ceil(7/22+1) = 1 个顶点 它是 {71}。

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

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


analysis


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

8. HeapSort()   //堆排序

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


分析:堆排序显然是O(N log N) - 一个最优的通过比较来排序的算法 

Quiz: In worst case scenario, HeapSort() is asymptotically faster than...

Bubble Sort
Selection Sort
Insertion Sort
Merge Sort

8-1. 讨论

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


讨论点:HeapSort()的缓存性能如何?

8-2. 答案

[This is a hidden slide]

8-3. PartialSort()

如果我们只想要二叉最大堆中最大的K个数,我们实际上可以调用O(log N)的 ExtractMax() K次。在目前显示的最大二叉堆上试试[未添加]。这个操作叫做PartialSort() (部分排序)。
简单分析:PartialSort() 的时间复杂度很明显是O(K log N),复杂度取决于输出的大小。

9. 一些额外内容

现在你已经到了最大二叉堆基础知识这章的结尾,我们希望你可以在探索模式中探索更多。
然而我们还有一些更有趣的最大二叉堆的挑战,这些在这章节列出。

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

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

如果我们只处理数字(包括这个只接受整数的动画),转换最大二叉堆变为最小二叉堆很容易 不需要改任何东西,反之亦然。
我们可以取每一个元素的相反数去重新构造一个二叉堆。如果最开始我们用的是最大二叉堆,那么结果就是最小二叉堆(忽视负号,见上图),反之亦然。

9-2. UpdateKey(i, newv)

对于一些优先队列的应用场景,我们需要修改(增加或降低)一个已经在(最大)二叉堆里的值的优先度。如果我们知道此值的序号i,我们可以利用以下简单的策略:更新A[i] = newv,然后shiftUp(i)shiftDown(i),只有一个恢复最大堆的动作会成功 - 如果newv > / < A[parent(i)]/A[i更大的子值] shiftUp(i)/shiftDown(i)会被触发。

所以,UpdateKey(i, newv)可以在O(log N)内完成,如果我们已知序号i

9-3. Delete(i)

对于一些优先队列的应用场景,我们需要修改(增加或降低)一个已经在(最大)二叉堆里的值的优先度。如果我们知道此值的序号i,我们可以利用以下简单的策略:更新A[i] = A[1]+1(一个比当前根更大的值)。然后shiftUp(i)(实际上是UpdateKey(i, A[1]+1)。这样会使序号i变成新的根,然后我们可以ExtractMax()一次来删除它。

所以,Delete(i)可以在O(log N)内完成,前提是我们已知序号i

讨论:对于UpdateKey(i, newv)Delete(i),如果我们只有oldv,必须搜索它在最大二叉树中的的位置,会怎样?可以比O(N)更快吗?

9-4. 答案

[This is a hidden slide]

9-5. 源代码

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

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

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

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


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

9-6. 在线测试

如果你想了解更多关于这个数据结构的有趣问题,你可以去这里做一些训练和测试 二叉堆 (不需要登录)。
NUS学生请登录并且通过这个单元的考试,相应的成就会被记录在你的账户里.

9-7. 在线评审练习

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


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

9-8. 讨论

[This is a hidden slide]

9-9. 令人震惊的东西

在漫长的最大二叉堆的课程之后,惊悚时刻到了...
最大二叉堆有可能不是实现优先队列最好的数据结构...
思考:所以用什么更好?

9-10. 答案

[This is a hidden slide]