-
【数据结构】堆及堆排序详解
1. 简介
堆（Heap）在计算机科学中可以表示内存的一部分，也是数据结构与算法中一种非常常用的数据结构。
尤其是在较大数据量的排序等问题中，堆排序经常被使用，因为堆排序的时间复杂度为
O(nlogn)。堆排序也是面试中经常被问到的对大量数据排序的算法，如海量数据选出TOP K等。堆的结构
堆是一棵完全二叉树，且分为 大顶堆 和 小顶堆 两种结构：大顶堆中根结点的值大于左右子结点的值；小顶堆中根结点的值小于左右子结点的值。大顶堆示例如下图所示：
2. 建堆和添加、删除操作
2.1 建堆
我们以如下所示的原始完全二叉树为例，详细描述大顶堆建堆的整过程。
给定的数字的初始序列为: 85、55、82、57、68、92、99、98、66、56
将它们按照树的层序从上到下、从左到右依次摆放就得到如上图所示的初始的完全二叉树（堆是一种完全二叉树）现在要调整这个初始堆，使它成为一个大顶堆。
调整的策略是：从最后一个结点开始从右向左、从下到上调增，使得父结点的值大于两个子结点的值。并且，对交换的子结点还要进行递归，使得它下面的子树仍然满足大顶堆的性质。1）56比它的父结点68的值下，因此56不需要调整；
2）66和98两个子结点的值和它们的父结点相比较，选择最大的值做父结点，将原来的父结点的值与最大值的根结点交换，如下图：
3）99和92与它们的父结点相比较，选择最大的做父结点，得到如下图
4）68和98与它们的父结点相比较，选择最大的98做父结点，即55和98交换。交换后还要对55进行递归，55比它的子结点小，继续调整，最终得到如下图：
5）99和98与它们的父结点相比较，选择最大的99做父结点，即将85与99交换。交换后还需要对85递归，最终得到如下图：
最终，所有结点都进行了调整，得到了大顶堆如下：
对树进行调整的代码
//heap为堆，n为元素个数，heap数组有效数字下标要从1开始 vector<int> heap; // 元素个数 int size; /** * 对 heap 数组在 [low, high] 范围进行向下调整 * 其中low为欲调整结点的下标，high一般为堆的最后一个元素的数组下标 */ void downAdjust(int low, int high) { int i = low, j = i * 2; // i为欲调整结点，j为其左孩子 while (j <= high) { //存在孩子结点 // 如果右孩子存在，且右孩子的值大于左孩子 if (j + 1 <= high && heap[j + 1] > heap[j]) { j = j + 1; // 让j存储右孩子下标 } // 如果孩子中最大的权值比欲调整结点i大 if (heap[j] > heap[i]) { swap(heap[i], heap[j]); // 交换最大权值的孩子与欲调整结点i i = j; //保持i为欲调整结点，j为其左孩子 j = i * 2; } else { break; // 孩子的权值均比欲调整结点i小，调整结束 } } }- 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
heap 数组下标的范围为 1~n。完全二叉树的叶子结点个数为
⌈n/2⌉，因此数组下标在[1, ⌊n/2⌋范围内的结点都是非叶子结点。于是可以从⌊n/2⌋号位开始倒着枚举结点，对每个遍历到的结点i进行 [i, n] 范围的调整。建堆代码
// 建堆 void createHeap() { for (int i = n / 2; i >= 1; i--) { downAdjust(i, n); } }- 1
- 2
- 3
- 4
- 5
- 6
2.2 删除堆顶元素操作
如果要删除堆中的最大元素（也就是删除堆顶元素），并且让其仍然保持堆的结构，那么只需要最后一个元素覆盖堆顶元素，然后对根结点进行调整即可。时间复杂度为
O(logn).// 删除堆顶元素 int deleteTop() { int res = heap[1]; heap[1] = heap[size--]; heap.pop_back(); downAdjust(1, size); return res; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
2.3 添加元素操作
添加元素操作：可以把要被添加的元素放在数组最后（也就是完全二叉树最后一个结点的后面），然后向上进行调整操作。
向上调整操作：总是把欲调整结点与父结点比较，如果权值比父结点大，那么就交换其与父结点，止痒反复比较，直到堆顶或者父结点的权值较大为止。时间复杂度为O(logn).// 对heap数组在[low, high] 范围进行向上调整 // 其中low一般设置为1，high表示欲调整结点的数组下标 void upAdjust(int low, int high) { int i = high, j = i / 2; // i为欲调整结点，j为其父结点 while (j >= low) { // 父结点在 [low, high] 范围内 // 父亲权值小于欲调整结点i的权值 if (heap[i] > heap[j]) { swap(heap[i], heap[j]); // 交换父结点和欲调整结点 i = j; // 保持i为欲调整结点，j为其父结点 j = i / 2; } else { break; // 父亲权值比欲调整结点i的权值大，调整结束 } } } // 添加元素x void insert(int x) { heap.push_back(x); // 让元素个数加1，然后将数组末位赋值为x size++; upAdjust(1, size); // 向上调整新加入的结点x }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
3. 堆排序
堆排序是使用堆结构对一个序列进行排序。
思路：堆顶元素是最大的，因此可以考虑取出堆顶元素，然后将堆的最后一个元素替换至堆顶，再进行一次针对堆顶元素的向下调整。如此重复，直到堆中只剩下一个元素为止。
// 堆排序 void heapSort() { createHeap(); // 建堆 for (int i = n; i >= 1; i--) { //倒着枚举，直到堆中只有一个元素 swap(heap[i], heap[1]); // 交换heap[i]与堆顶 downAdjust(1, i - 1); // 调整堆顶 } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
4. 测试
C++
#include#include using namespace std; class HeapSort { public: vector<int> heap; // 存储元素 int size; // 元素个数 HeapSort(vector<int> &nums) { size = (int) nums.size(); heap.push_back(-1); // 堆中为便于计算父子结点关系，数组下标需要从1开始 for (int i = 0; i < size; i++) { heap.push_back(nums[i]); } } void downAdjust(int low, int high) { int i = low, j = i * 2; while (j <= high) { if (j + 1 <= high && heap[j + 1] > heap[j]) { j = j + 1; } if (heap[j] > heap[i]) { swap(heap[i], heap[j]); i = j; j = i * 2; } else { break; } } } void createHeap() { for (int i = size / 2; i >= 1; i--) { downAdjust(i, size); } } int deleteTop() { int res = heap[1]; heap[1] = heap[size--]; heap.pop_back(); downAdjust(1, size); return res; } void upAdjust(int low, int high) { int i = high, j = i / 2; while (j >= low) { if (heap[i] > heap[j]) { swap(heap[i], heap[j]); i = j; j = i / 2; } else { break; } } } void insert(int x) { heap.push_back(x); size++; upAdjust(1, size); } void heapSort() { createHeap(); for (int i = size; i >= 1; i--) { swap(heap[i], heap[1]); downAdjust(1, i - 1); } } }; int main() { vector<int> nums = {9, 7, 5, 3, 1, 2, 4, 6, 8}; HeapSort heapSort(nums); // 打印出元素序列 for (int i = 1; i <= heapSort.size; i++) { cout << heapSort.heap[i] << " "; } cout << endl; // 建堆 heapSort.createHeap(); // 删除堆顶元素，被删除的应为9 int res = heapSort.deleteTop(); cout << "top element: " << res << endl; // 接着删除堆顶元素，被删除的应为8 res = heapSort.deleteTop(); cout << "top element: " << res << endl; // 接着删除堆顶元素，被删除的应为7 res = heapSort.deleteTop(); cout << "top element: " << res << endl; // 向堆中插入新元素-8 heapSort.insert(-8); // 向堆中插入新元素-2 heapSort.insert(-2); // 对堆中剩余元素进行堆排序 heapSort.heapSort(); // 打印出堆排序后的元素序列 for (int i = 1; i <= heapSort.size; i++) { cout << heapSort.heap[i] << " "; } return 0; } - 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
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
测试结果
JAVA
/** * @date 2022/8/15 */ public class HeapSort { /** * 存储数据 */ private int[] heap; /** * 堆元素个数 */ private int size; public HeapSort(int[] nums) { size = nums.length; heap = new int[size + 1]; for (int i = 0; i < nums.length; i++) { heap[1 + i] = nums[i]; } } public void downAdjust(int low, int high) { int i = low, j = i * 2; while (j <= high) { if (j + 1 <= high && heap[j + 1] > heap[j]) { j = j + 1; } if (heap[j] > heap[i]) { int tmp = heap[i]; // 交换i和j heap[i] = heap[j]; heap[j] = tmp; i = j; j = i * 2; } else { break; } } } public void createHeap() { for (int i = size / 2; i >= 1; i--) { downAdjust(i, size); } } public int deleteTop() { int res = heap[1]; heap[1] = heap[size--]; downAdjust(1, size); return res; } public void upAdjust(int low, int high) { int i = high, j = i / 2; while (j >= low) { if (heap[i] > heap[j]) { int tmp = heap[i]; // 交换heap[i]和heap[j] heap[i] = heap[j]; heap[j] = tmp; i = j; j = i / 2; } else { break; } } } public void insert(int x) { if (size + 1 >= heap.length) { int[] newHeap = new int[size * 2]; System.arraycopy(heap, 0, newHeap, 0, size); heap = newHeap; } heap[++size] = x; upAdjust(1, size); } public void heapSort() { for (int i = size; i >= 1; i--) { int tmp = heap[1]; heap[1] = heap[i]; heap[i] = tmp; downAdjust(1, i - 1); } } // 打印heap数组元素，测试用 public void printHeap() { for (int i = 1; i <= size; i++) { System.out.print(heap[i] + " "); } System.out.println(); } public static void main(String[] args) { int[] nums = {9, 7, 5, 3, 1, 2, 4, 6, 8}; HeapSort heapSort = new HeapSort(nums); // 打印出元素序列 heapSort.printHeap(); // 建堆 heapSort.createHeap(); // 删除堆顶元素，被删除的应为9 int res = heapSort.deleteTop(); System.out.println("top element: " + res); // 接着删除堆顶元素，被删除的应为8 res = heapSort.deleteTop(); System.out.println("top element: " + res); // 接着删除堆顶元素，被删除的应为7 res = heapSort.deleteTop(); System.out.println("top element: " + res); // 向堆中插入新元素-8 heapSort.insert(-8); // 向堆中插入新元素-2 heapSort.insert(-2); // 对堆中剩余元素进行堆排序 heapSort.heapSort(); // 打印出堆排序后的元素序列 heapSort.printHeap(); } }- 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
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
测试结果
5. TOP K 问题
TOP K问题是面试中常常被问到的问题，从大量的数据中，找出最小的或者最大的几个值，这就可以采用
堆来实现。例如，给定1,000,000个整数，要求从中找出最大的10个数。
我们可以首先用前10个数建立一个size为10的
小顶堆，即堆顶元素是10个数中最小的。然后依次取出后面的10 ~ 1,000,000个数，将其与小顶堆的堆顶元素进行比较：- 如果小于等于堆顶元素，则说明这个数比堆中的10个元素都小，跳过；
- 如果大于堆顶元素，则用该数替换掉小顶堆的堆顶元素，然后对小顶堆从堆顶向下做一次调整，使得还是形成小顶堆。
这样，当所有的数都验证完后，小顶堆中的10个元素就是这1,000,000个元素中最大的10个元素。
并且，当数据量非常大，内存无法一次性载入时仍然可以使用堆来获取 TOP K，将硬盘中的数据分块的载入内存，再与堆顶元素进行比较、替换、调整。
参考文献
《算法笔记》，胡凡、曾磊等.
-
相关阅读:
相交链表Java
云图说丨初识华为云微服务引擎CSE
如何在IPhone 14、14 Pro和14 Pro Max上添加屏幕锁定
源码分析RocketMQ之Broker-内存映射刷盘流程
力控关节机器人（关节扭矩传感器力控）
【面经】米哈游数据开发面经
从头开始实现一个留言板-README
docker network怎么创建桥接网络
行情分析——加密货币市场大盘走势（11.10）
Kubernetes 笔记 / 入门 / 生产环境 / 用部署工具安装 Kubernetes / 用 kubeadm 启动集群 / 两种高可用拓扑
- 原文地址：https://blog.csdn.net/qq_27198345/article/details/126310992
