数据结构笔记：优先级队列 (完全二叉堆、左式堆)

发表于 | 分类于

概述

  1. 完全二叉堆
  2. 左式堆
小试牛刀
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 单选题 
1. The method for inserting elements in a full binary heap is
在完全二叉堆中插入元素的方法是   A

A. 插入到底层，上滤
B. 插入到根节点，下滤
C. 直接插入到底层
D. 直接插入到根节点

2. 规模为n的完全二叉堆中删除元素的时间复杂度为：C

A. O(nlgn)
B. O(n)
C. O(lgn)
D. O(1)

3. 使用自上而下的上滤建立规模为n的完全二叉堆，最坏时间复杂度为：A

A. O(nlgn)
B. O(n)
C. O(lgn)
D. O(1)

4. Floyd建堆算法建立规模为n的完全二叉堆的时间复杂度为：B

A. O(nlgn)
B. O(n)
C. O(lgn)
D. O(1)

5. 如何用堆来实现排序：A

A. 建堆后不断调用delMax()
B. 建堆后不断调用getMax()
C. 建堆后不断调用insert()
D. 建堆


6. 相对于完全二叉堆，左式堆存在的意义是：C

A. 高效的插入
B. 高效的删除
C. 高效的合并
D. 高效的查找

image-20250812000010744

image-20250811232141585

image-20250811232240198

用向量实现的效率：

image-20250811235235807

有序向量实现的效率：

image-20250811235501789

用列表实现的效率：

image-20250811235540378

BBST实现的效率：
image-20250811235836094

完全二叉堆

完全二叉树：

image-20250812000218662

完全二叉堆

image-20250812004344806

image-20250812004450871

image-20250812004726811

完全二叉堆：插入和上滤

image-20250813220852795

实例：

image-20250813221203365

代码实现：

1
2
3
4
template <typename T> void PQ_ComplHeap<T>::insert( T e ) { //将词条插入完全二叉堆中
   Vector<T>::insert( e ); //将新词条接至向量末尾
   percolateUp( _elem, _size - 1 ); //再对该词条实施上滤调整
}
1
2
3
4
5
6
7
8
template <typename T> Rank percolateUp( T* A, Rank i ) { //对词条A[i]做上滤，0 <= i < _size
   while ( 0 < i ) { //在抵达堆顶之前，反复地
      Rank j = Parent( i ); //考查[i]之父亲[j]
      if ( !( A[j] < A[i] ) ) break; //一旦父子顺序，上滤旋即完成；否则
      swap( A[i], A[j] ); i = j; //父子换位，并继续考查上一层
   } //while
   return i; //返回上滤最终抵达的位置
}

效率：
image-20250813221907577

完全二叉堆：删除和下滤

image-20250813225051835

实例：

image-20250813225741847

代码实现：

1
2
3
4
5
template <typename T> T PQ_ComplHeap<T>::delMax() { //取出最大词条
   swap( _elem[0], _elem[--_size] ); //堆顶、堆尾互换（_size的递减，不致引发shrink()）
   percolateDown( _elem, _size, 0 ); //新堆顶下滤
   return _elem[_size]; //返回原堆顶
}
1
2
3
4
5
6
7
//对向量前n个词条中的第i个实施下滤，i < n
template <typename T> Rank percolateDown( T* A, Rank n, Rank i ) {
   Rank j; // i及其（至多两个）孩子中，堪为父者
   while ( i != ( j = ProperParent( A, n, i ) ) ) //只要i非j，则
      swap( A[i], A[j] ), i = j; //二者换位，并继续考查下降后的i
   return i; //返回下滤抵达的位置（亦i亦j）
}

效率：

image-20250813230333213

image-20250816102700594

左式堆

堆合并：将堆A和堆B合二为一

NPL

image-20250816200528874

image-20250816200607124

image-20250816200715089

习题

1
2
3
4
5
6
1. 使用以下哪种数据结构实现优先级队列的insert, getMax, delMax接口均可达到O(lgn)的时间复杂度？  D

A. 向量
B. 有序向量
C. 散列表
D. 平衡二叉搜索树
1
2
3
4
5
6
2. 栈作为优先级队列的一种特殊情况，其中元素的优先级：A

A. 先入栈者优先级低
B. 先入栈者优先级高
C. 所有元素优先级相同
D. 元素优先级之间没有确定的关系
1
2
3
4
5
6
3. 完全二叉树从整体上看的形态是：B

A. 完整的三角形
B. 缺右角的三角形
C. 缺左角的三角形
D. 底部呈锯齿状的三角形
1
2
3
4
5
6
4. 完全二叉堆在物理上是向量，其所存储的元素次序是  D

A. 完全二叉树的先序遍历次序
B. 完全二叉树的中序遍历次序
C. 完全二叉树的后序遍历次序
D. 完全二叉树的层次遍历次序
1
2
3
4
5
6
5. 在完全二叉堆中（大顶堆），不正确的是  D

A. 任何节点的数值不超过其父亲
B. 兄弟节点之间的没有确定的大小关系
C. 节点的数值不超过其任何一个祖先
D. 整个堆中的最大元素在底部的叶子节点
1
2
3
4
5
6
6. 当前完全二叉堆物理上作为向量是{10, 5, 8, 3, 2, 7}，插入新元素9后变为： D

A. {2, 3, 5, 7, 8, 9, 10}
B. {10, 9, 8, 7, 5, 3, 2}
C. {10, 5, 8, 3, 2, 7, 9}
D. {10, 5, 9, 3, 2, 7, 8}
1
2
3
4
5
6
7. 当前完全二叉堆物理上作为向量是{10, 5, 8, 3, 2, 7},调用delMax()后变为： C

A. {5, 8, 3, 2, 7}
B. {2, 3, 5, 7, 8}
C. {8, 5, 7, 3, 2}
D. {8, 7, 5, 3, 2}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
8. Existing n elements need to be organized into a complete binary stack
现有n个元素需要组织成一个完全二叉堆

If you use the method of constantly inserting all the elements
若使用不断插入所有元素的方法

The whole process is:
整个过程是:   A


A. Top-down percolateUp自上而下的上滤
B. Top-down percolateDown自上而下的下滤
C. Down-top percolateUp自下而上的上滤
D. Down-top percolateDown自下而上的下滤

9. 时间复杂度为:  O(nlgn)

O(lgn)
O(n)
O(nlgn)
O(n^2)

10. 若使用Floyd算法

The whole process is:整个过程是: D


A. Top-down percolateUp自上而下的上滤
B. Top-down percolateDown自上而下的下滤
C. Down-top percolateUp自下而上的上滤
D. Down-top percolateDown自下而上的下滤

11. 时间复杂度为:  O(n)

O(lgn)
O(n)
O(nlgn)
O(n^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
12. 堆排序在流程上类似于以前学过的哪种排序？  选择排序

Selection sort
选择排序
Insertion sort
插入排序
Bubble sort
冒泡排序
Merge sort
归并排序

13. 而在渐进时间复杂度上与哪种排序相同？  归并排序

Selection sort
选择排序
Insertion sort
插入排序
Bubble sort
冒泡排序
Merge sort 
归并排序

14. 堆排序的时间复杂度为:  O(nlgn)

O(n)
O(nlgn)
O(nlgnlgn)
O(n^2)

15. 空间复杂度为（不包括输入本身所占的空间）  O(1)

O(1)
O(n)
O(nlgn)
O(n^2)

zhangzezhong

学习自：清华大学邓俊辉老师《数据结构 下》课程第十二章 优先级队列