湘潭大学数据结构课件pptCh06PriorityQueues(Heaps)

1、Review队列先进先出设想：发送到打印机的文档放到队列中，如果希望先打印重要的或短的文档？操作系统调度程序使用队列，重要的或短的作业能优先吗？第六章 优先队列（堆） 删除具有最高删除具有最高/ /最低优先级的元素最低优先级的元素1 ADT 模型模型数据对象集数据对象集: 一个有限的有序表，包含零个或多个元素。一个有限的有序表，包含零个或多个元素。数据操作集数据操作集: PriorityQueue Initialize( int MaxElements ); void Insert( ElementType X, PriorityQueue H ); ElementType DeleteMin

2、( PriorityQueue H ); ElementType FindMin( PriorityQueue H ); 【定义定义】 “优先队列优先队列” （Priority Queue）是特殊的）是特殊的“队列队列”，从堆中，从堆中取出元素的顺序是依照元素的取出元素的顺序是依照元素的优先权（关键字）优先权（关键字）大小，而不是元素进入大小，而不是元素进入队列的先后顺序。采用完全二叉树存储的优先队列队列的先后顺序。采用完全二叉树存储的优先队列 称为称为堆堆（Heap）。）。2 简单的实现简单的实现 数组数组 :Insertion 元素插入在末尾元素插入在末尾 ( 1 )Deletion 查找

3、最大（或最小）关键字查找最大（或最小）关键字 ( n ) 从数组中删除需要移动元素从数组中删除需要移动元素 O( n ) 链表链表:Insertion 元素总是插入链表的头部元素总是插入链表的头部 ( 1 )Deletion 查找最大（或最小）关键字查找最大（或最小）关键字 ( n ) 删去结点删去结点 ( 1 ) 有序数组有序数组:Insertion 找到合适的位置找到合适的位置 O( n )或或O(logn) 移动元素并插入移动元素并插入 O( n )Deletion 删去最后一个元素删去最后一个元素 ( 1 ) 有序链表有序链表:Insertion 找到合适的位置找到合适的位置 O( n

4、 ) 插入元素插入元素 ( 1 )Deletion 删除首元素或最后元素删除首元素或最后元素 ( 1 )由于由于Deletion的次数从不多余的次数从不多余Insertion的次数，链表可能是的次数，链表可能是更好的想法。更好的想法。 二叉查找树二叉查找树:2 简单的实现简单的实现其实其实AVL 的许多操作的许多操作对优先队列而言并不是必须的对优先队列而言并不是必须的.而且而且, 指针操作总带有某些潜在的危险指针操作总带有某些潜在的危险 好好! 好注意好注意! 插入和删除都只需要插入和删除都只需要O(log N) .可是要注意可是要注意-插入是随机的插入是随机的, 而删除不是。而删除不是。 我

5、们总是假定删除最大的元素我们总是假定删除最大的元素. 呃哦呃哦 还不行吗还不行吗? 哦哦, 对呀对呀, 我们总是从左子树删除我们总是从左子树删除.而我们还必须保持树的平衡而我们还必须保持树的平衡 我想你是不是又有更好的想法了我想你是不是又有更好的想法了?现在你开始懂现在你开始懂 我了我了 你越来越聪明啦你越来越聪明啦! 像像AVL 树这种平衡二叉树并不一定是树这种平衡二叉树并不一定是个坏主意，因为我们只需要增加常数的个坏主意，因为我们只需要增加常数的运行时间。可是运行时间。可是 3 二叉堆二叉堆1. 结构性质结构性质:【定义定义】一棵具有一棵具有 n 个结点，高度为个结点，高度为 h 的二叉树

6、是的二叉树是完全二完全二叉树叉树，当且仅当它的结点编号与高度为，当且仅当它的结点编号与高度为 h 的满二叉树结点的满二叉树结点编号能一一对应。编号能一一对应。489510116121371415231一棵一棵高度为高度为 h 的完全二叉树结点数为的完全二叉树结点数为至至个。个。2h2h+1 1h = log N 数组实现数组实现: BT n + 1 ( BT 0 未使用未使用)DHIEJFGBCABT01A2B3C4D5E6F7G8H9I10J1112133 二叉堆二叉堆【引理引理】如果一棵具有如果一棵具有 n 个结点的完全二叉树是顺序实现个结点的完全二叉树是顺序实现的，那么对任意位置编号的，

7、那么对任意位置编号 i 的的结点，结点， 1 i n，有：有： niniiichildrightniniiichildleftiiiiparent12 ifNone12 if12)(_ ofindex (3)2 ifNone2 if2)(_ ofindex (2)1 ifNone1 if2)( ofindex (1)3 二叉堆二叉堆PriorityQueue Initialize( int MaxElements ) PriorityQueue H; if ( MaxElements Elements = malloc( MaxElements + 1 ) * sizeof( ElementT

8、ype ); if ( H-Elements = NULL ) return FatalError( Out of space! ); H-Capacity = MaxElements; H-Size = 0; H-Elements 0 = MinData; /* set the sentinel */ return H; 3 二叉堆二叉堆2. 堆序性质堆序性质:【定义定义】一棵一棵最小树最小树是树中任意结点的关键字不大于它是树中任意结点的关键字不大于它的孩子结点的关键字（如果有的话）。一个的孩子结点的关键字（如果有的话）。一个最小堆最小堆是是一棵一棵完全二叉树完全二叉树，同时也是一棵，同时也

9、是一棵最小树最小树。Note: 类似地，我们可以声明一个类似地，我们可以声明一个最大堆最大堆，只要更改，只要更改堆序性质即可。堆序性质即可。96531234一个最大堆一个最大堆102050831234一个最小堆一个最小堆最大关键字最大关键字最小关键字最小关键字3 二叉堆二叉堆3. 基本的堆操作基本的堆操作: insertion1012152012341856 算法梗概算法梗概:由于堆必须是完全二叉树，由于堆必须是完全二叉树，这是唯一可能插入这是唯一可能插入新结点的位置。新结点的位置。情形情形 1 : new_item = 212120211720101791099103 二叉堆二叉堆/* H-

10、Element 0 is a sentinel */ void Insert( ElementType X, PriorityQueue H ) int i; if ( IsFull( H ) ) Error( Priority queue is full ); return; for ( i = +H-Size; H-Elements i / 2 X; i /= 2 ) H-Elements i = H-Elements i / 2 ; H-Elements i = X; 上滤上滤Percolate up比比swap快快H-Element 0 是一个是一个哨兵哨兵 ，即比堆中最小的值，即比堆

11、中最小的值还要小。还要小。T (N) = O ( log N )3 二叉堆二叉堆 DeleteMin 算法梗概算法梗概:101215201234185 move 18 up to the root18 find the smaller child of 18121818121518Elements 0 ; MinElement = H-Elements 1 ; /* save the min element */ LastElement = H-Elements H-Size- ; /* take last and reset size */ for ( i = 1; i * 2 Size;

12、i = Child ) /* Find smaller child */ Child = i * 2; if (Child != H-Size & H-ElementsChild+1 ElementsChild) Child+; if ( LastElement H-Elements Child ) /* Percolate one level */ H-Elements i = H-Elements Child ; else break; /* find the proper position */ H-Elements i = LastElement; return MinElem

13、ent; 下滤下滤Percolate down省略这个条件，省略这个条件，会发生什么？会发生什么？通过添加另一个通过添加另一个哨兵，能否去掉哨兵，能否去掉这个测试这个测试?3 二叉堆二叉堆4. 其他的堆操作其他的堆操作:Note: 查找除最小元外的任何元素都需对整个堆进行线查找除最小元外的任何元素都需对整个堆进行线性搜索。性搜索。 DecreaseKey ( P, , H )将堆将堆 H 中位置中位置 P 处的结点关键字减小处的结点关键字减小 因此我的程序可以以更高优先级运行因此我的程序可以以更高优先级运行 .sys. admin. IncreaseKey ( P, , H )Percolat

14、e upsys. admin.将堆将堆 H 中位置中位置 P 处的结点关键字增加处的结点关键字增加 将过度消耗将过度消耗CPU时间的进程降低优先级。时间的进程降低优先级。Percolate down3 二叉堆二叉堆 Delete ( P, H )将堆将堆 H 中位置中位置 P 处的结点删除处的结点删除 当一个进程当一个进程由用户中止（非正常终止）时，它必须从优先由用户中止（非正常终止）时，它必须从优先队列中除去。队列中除去。sys. admin.DecreaseKey(P, , H); DeleteMin(H) BuildHeap ( H )将将 N 个关键字以任意顺序放到一个空堆个关键字以任

15、意顺序放到一个空堆H中中。sys. admin.N successive Insertions ? 那太。慢了那太。慢了!301002010906070501201101401308040150150, 80, 40, 30, 10, 70, 110, 100, 20, 90, 60, 50, 120, 140, 130PercolateDown (7)PercolateDown (6)5070PercolateDown (5)PercolateDown (4)2030PercolateDown (3)PercolateDown (2)80108060PercolateDown (1)1501

16、01502015030T (N) = ?3 二叉堆二叉堆【定理定理】对高度为对高度为 h ，包含，包含 2h+1 1 个结点的满二叉树，结个结点的满二叉树，结点高度之和为点高度之和为 2h+1 1 (h + 1).T ( N ) = O ( N )4 优先队列的应用优先队列的应用例例1选择问题：已知一个有选择问题：已知一个有N个元素的表，给定一个整个元素的表，给定一个整数数k，找到表中第，找到表中第k大的元素。大的元素。你能想到几种方法来解决这个问题？你能想到几种方法来解决这个问题？它们各自的时间复杂度是多少？它们各自的时间复杂度是多少？5 d-堆堆- 所有的结点都有所有的结点都有 d 个孩子

17、个孩子315136517892741091113-heapQuestion: d 是否越大越好是否越大越好?Note: 1. DeleteMin 将需要进行将需要进行 d 1 次比较来找出最小的孩子。因次比较来找出最小的孩子。因此总的时间复杂度将会提高到此总的时间复杂度将会提高到 O(d logd N). 2.*2 或或 /2 仅仅需要一次仅仅需要一次移位移位，但，但 *d 和和 /d 不能通过移位实现不能通过移位实现。 3. 当优先队列太大不能完全装入主存的时候，当优先队列太大不能完全装入主存的时候，d-堆是很有用的。堆是很有用的。4. 在实践中在实践中4-堆可以胜过二叉堆。堆可以胜过二叉堆

18、。6 左式堆左式堆 Heap: 结构性质结构性质 + 堆序性质堆序性质Target : 加速合并操作。加速合并操作。 必须把一个数组拷贝到另一个数组中去必须把一个数组拷贝到另一个数组中去 (N) 使用使用指针指针 使所有其他的操作变慢使所有其他的操作变慢左式堆左式堆: 堆序性质堆序性质 不变不变 结构性质结构性质 二叉树，且趋向于非常二叉树，且趋向于非常不平衡不平衡6 左式堆左式堆【定义定义】任意节点任意节点X的的零路径长零路径长, Npl(X) 是从是从X到一个没有两个儿子到一个没有两个儿子的结点的最短路径的长。的结点的最短路径的长。Npl(NULL) = 1.Note: Npl(X) =

19、min Npl(C) + 1 for all C as children of X 【定义定义】左式堆性质左式堆性质是：对堆中的每一个结点是：对堆中的每一个结点X，左儿子左儿子的零路径的零路径长长至少至少与与右儿子右儿子的零路径长的零路径长一样大一样大。000101 0010101 偏重于使树偏重于使树向左向左增增加深度。加深度。6 左式堆左式堆【定理定理】在右路径上有在右路径上有 r 个结点的左式树必然至少有个结点的左式树必然至少有 2r 1 个结点。个结点。证明证明: 数学归纳法，数学归纳法，p. 146.Note: N 个结点的左式树有一条右路径最多包含个结点的左式树有一条右路径最多包含

20、 log(N+1) 个结点。个结点。 所有的工作在所有的工作在右路径右路径上进行，保证树深较上进行，保证树深较短短。Trouble makers: Insert 和和 MergeNote: Insertion 只是只是 merge 的特殊情形。的特殊情形。6 左式堆左式堆struct TreeNode ElementType Element;PriorityQueue Left;PriorityQueue Right;int Npl; ; 声明声明: Merge (递归实现递归实现): 3102114238172661218243373718H1H2Step 1: Merge( H1-Righ

21、t, H2 )8172661218243371837Step 2: Attach( H2, H1-Right )3102114238172661218243371837Step 3: 必要的话，必要的话，Swap(H1-Right, H1-Left ) 6 左式堆左式堆PriorityQueue Merge ( PriorityQueue H1, PriorityQueue H2 ) if ( H1 = NULL ) return H2;if ( H2 = NULL ) return H1;if ( H1-Element Element ) return Merge1( H1, H2 );el

22、se return Merge1( H2, H1 );static PriorityQueueMerge1( PriorityQueue H1, PriorityQueue H2 ) if ( H1-Left = NULL ) /* single node */H1-Left = H2;/* H1-Right is already NULL and H1-Npl is already 0 */else H1-Right = Merge( H1-Right, H2 ); /* Step 1 & 2 */if ( H1-Left-Npl Right-Npl )SwapChildren( H

23、1 );/* Step 3 */H1-Npl = H1-Right-Npl + 1; /* end else */return H1;如果如果Npl 没有更新没有更新会怎样呢？会怎样呢？Tp = O(log N)6 左式堆左式堆 Merge (非递归实现非递归实现): 3102114238172661218243373718H1H2Step 1: 对右路径上的结点排序，并保对右路径上的结点排序，并保持他们的左儿子不变。持他们的左儿子不变。3102114236121824337371881726Step 2: 必要时交换结点左右子树。必要时交换结点左右子树。3102114236121824337

24、371881726 DeleteMin: p.150. Step 1: 删除根删除根Step 2: Merge两棵子树两棵子树Tp = O(log N)7 斜堆斜堆- 左式堆的简单版本左式堆的简单版本Target : 任意任意 M 次连续操作最多花费次连续操作最多花费 O(M log N) 时间。时间。 Merge: 总是总是交换左右孩子，除了右路径上交换左右孩子，除了右路径上最大的结点最大的结点外。不考虑外。不考虑 Npl。3102114238172661218243373718H1H23102114236121824337372681718并不是特殊情形，而并不是特殊情形，而是自然递归实现

25、时的是自然递归实现时的终止。终止。31021142361218243318737268177 斜堆斜堆【例例2】Insert 1515102136121824331873726817142315 Merge (非递归实现非递归实现): 3102114238172661218243373718H1H231021142361218243373726817187 斜堆斜堆Note: 斜堆的优点是斜堆的优点是不需要附加的空间不需要附加的空间来保留路径长以及来保留路径长以及不需要测试不需要测试确定何时交换孩子。确定何时交换孩子。 精确确定左式堆和斜堆的精确确定左式堆和斜堆的期望右路径长期望右路径长是一个

26、未解决的问题。是一个未解决的问题。常数常数! 所以一次插入花费所以一次插入花费 O(log N) 时间并时间并不够好不够好！我们已经有了足够多的队列了，我们已经有了足够多的队列了，为什么要使用为什么要使用二项队列二项队列？ O(log N) 有问题吗有问题吗? 根据定理根据定理 6.1 , 总的时间是总的时间是 O(N)插入插入 N 个关键字到个关键字到一个空的二叉堆，一个空的二叉堆，总共总共需要花费多少时间？需要花费多少时间？ 那么平均时间是？那么平均时间是？8 二项队列二项队列 结构结构: 一个二项队列并非一个二项队列并非一棵一棵堆序树，而是堆序树的堆序树，而是堆序树的集合集合，称为，称为

27、森林森林。每。每棵堆序树是一棵棵堆序树是一棵二项树二项树。高度为高度为 0 的二项树是一棵单结点树。的二项树是一棵单结点树。高度为高度为 k 的二项树的二项树Bk 通过将一棵二项树通过将一棵二项树 Bk 1 附接到另一棵二项树附接到另一棵二项树Bk 1的根上而构成。的根上而构成。B0B1B2B3 Bk 包含一个根和包含一个根和 个子树个子树, kB0, B1, , Bk 1 。Bk 恰好有恰好有 个结点。而深度个结点。而深度 d 处的结点数是处的结点数是 。2kkd二项系数二项系数在在左式堆左式堆和和斜堆斜堆中，中，插入的插入的平均时间平均时间是？是？8 二项队列二项队列【例例3】用二项树的集

28、合实现一个大小为用二项树的集合实现一个大小为 13 的优先队列。的优先队列。Bk 结构结构 + 堆序堆序 + 任意高度上最多有一棵二项树任意高度上最多有一棵二项树 用二项树的集合用二项树的集合唯一唯一地表示地表示任意大小任意大小的优先队列的优先队列方法方法:13 = 20 + 0 21 + 22 + 23 = 11012B0B1B2B3132351246512212465142616188 二项队列二项队列 操作实现操作实现: FindMin: 最小元是某一棵树的最小元是某一棵树的根根。最多有最多有 个根，因此个根，因此 Tp = O( ).log Nlog NNote: 如果我们记住最小元，

29、并在其他操作期间变化时更新它，那如果我们记住最小元，并在其他操作期间变化时更新它，那么可以么可以O(1)的时间执行的时间执行FindMin。 Merge: H1H213122124651618142623512465H11 1 0 2 = 6+ 1 1 1 2 = 71130c142616181c12212465235124651Tp = O( )log N必须将这些树放在必须将这些树放在按照按照高度排序高度排序的二项队列中。的二项队列中。8 二项队列二项队列 Insert: Merge的特殊情形。的特殊情形。 【例例4】将将 1, 2, 3, 4, 5, 6, 7 插入到一个初始为空的队列中

30、。插入到一个初始为空的队列中。123412345657Note: 如果元素将要插入的那个优先队列中不存在的最小的二项树是如果元素将要插入的那个优先队列中不存在的最小的二项树是 Bi ，那么运行时间，那么运行时间Tp = Const (i + 1)。 在初始为空的二项队列上进行在初始为空的二项队列上进行 N 次次插入插入最多将花费最多将花费 O(N) 时间。时间。因此因此平均平均时间是时间是常数常数。8 二项队列二项队列 DeleteMin ( H ):H13142616181221246523512465H1314261618Step 1: FindMin in BkStep 2: Remov

31、e Bk from HStep 3: Remove root from Bk 21246523512465H”Step 4: Merge (H, H”)23512465H1321246514261618/* O(log N) */* O(1) */* O(log N) */* O(log N) */8 二项队列二项队列 实现实现: 二项队列二项队列 = 二项树的二项树的数组数组DeleteMinMerge快速找到所有快速找到所有子树子树诸儿子按照大小诸儿子按照大小排序排序操作操作特征特征解决方法解决方法儿子兄弟表示法儿子兄弟表示法新的树将是最大的一棵，新的树将是最大的一棵，因此以因此以大小递减

32、大小递减方式保方式保持这些子树。持这些子树。1313142616181221246523512465H012341416261812242165232451658 二项队列二项队列typedef struct BinNode *Position;typedef struct Collection *BinQueue;typedef struct BinNode *BinTree; /* missing from p.176 */struct BinNode ElementType Element;Position LeftChild;Position NextSibling; ;struct

33、Collection int CurrentSize; /* total number of nodes */BinTreeTheTrees MaxTrees ; ;8 二项队列二项队列BinTreeCombineTrees( BinTree T1, BinTree T2 ) /* merge equal-sized T1 and T2 */if ( T1-Element T2-Element )/* attach the larger one to the smaller one */return CombineTrees( T2, T1 );/* insert T2 to the fron

34、t of the children list of T1 */T2-NextSibling = T1-LeftChild;T1-LeftChild = T2;return T1;Tp = O( 1 )1224216514162618T1T28 二项队列二项队列BinQueue Merge( BinQueue H1, BinQueue H2 )BinTree T1, T2, Carry = NULL; int i, j;if ( H1-CurrentSize + H2- CurrentSize Capacity ) ErrorMessage();H1-CurrentSize += H2- Cur

35、rentSize;for ( i=0, j=1; jCurrentSize; i+, j*=2 ) T1 = H1-TheTreesi; T2 = H2-TheTreesi; /*current trees */ switch( 4*!Carry + 2*!T2 + !T1 ) /* assign each digit to a tree */case 0: /* 000 */ case 1: /* 001 */ break;case 2: /* 010 */ H1-TheTreesi = T2; H2-TheTreesi = NULL; break;case 4: /* 100 */ H1-TheTreesi = Carry; Carry = NULL; break;case 3: /* 011 */ Carry = CombineTrees( T1, T2 ); H1-TheTreesi = H2-TheTreesi = NULL; break;case 5: /* 101 */ Carry = CombineTrees( T1, Carry ); H1-TheTreesi = NULL; break;case 6: /* 110 */ Carry