堆及其应用(一)
预先掌握
堆的定义
- 堆:是一种特殊的树形数据结构,通常指的是二叉堆,可以被看作一棵完全二叉树。堆的特点是每个节点的值都大于等于(对于最大堆)或小于等于(对于最小堆)其子节点的值。堆的根节点包含最大值(最大堆)或最小值(最小堆)。
- 用途:堆:主要用于实现优先队列,支持高效地从队列中提取最大或最小元素。堆还常用于堆排序算法中,该算法利用堆的性质实现了快速排序。此外,堆在带权任务调度、频率统计和数据压缩等领域也有重要应用。
"堆" 在计算机科学和日常生活中都有多种含义,但在这里我主要讨论它在计算机科学中的数据结构和算法中的应用。
堆(Heap) 是一种特殊的树形数据结构,通常是一个完全二叉树。堆有两个主要类型:
- 最大堆(Max Heap):在最大堆中,对于除了根以外的每个节点 i,都有
A[parent(i)] >= A[i]
,其中A
是包含堆元素的数组,parent(i)
是返回节点 i 的父节点索引的函数。这意味着根节点包含堆中的最大值。 - 最小堆(Min Heap):在最小堆中,对于除了根以外的每个节点 i,都有
A[parent(i)] <= A[i]
。这意味着根节点包含堆中的最小值。
堆的一个重要特性是它们可以通过数组高效地实现,因为它们是完全二叉树。给定一个节点在数组中的索引 i(通常从 0 开始),其左子节点的索引是 2i+1,右子节点的索引是 2i+2,其父节点的索引是 (i-1)/2(在向下取整的情况下)。
堆的性质
操作
[【堆及其应用一】大根堆]
【算法分析】 用输入的 n 个数建立一个大根堆,然后 for 循环 从 1∼n 输出堆数组。 【参考代码】 #include<bits/stdc++.h> using namespace std; const int maxn = 1e5 + 9; int heap[maxn], heap_size; void put(int d) { int son, pa; heap[++heap_size] = d;//新增一个结点,值为d son = heap_size; while (son > 1) { //向上调整,使其满足大根堆的性质 pa = son >> 1; //找到父节点 if (heap[son] <= heap[pa]) break; //如果父节点的值大于等于儿子结点,调整完毕 swap(heap[son], heap[pa]); //向上调整 son = pa; } } int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { int x; cin >> x; put(x); } for (int i = 1; i <= n; i++) cout << heap[i] << " "; return 0; }View Code
【堆及其应用一】排序1
【算法分析】 建立一个大根堆,每次输出堆顶的元素,然后将堆顶元素删除(删除之后要调整堆使得满足大根堆的性质),这样就可以使得元素从大到小排序。 【参考代码】 #include<bits/stdc++.h> using namespace std; const int maxn = 1e5 + 9; int heap[maxn], heap_size; void put(int d) { int son, pa; heap[++heap_size] = d;//新增一个结点,值为d son = heap_size; while (son > 1) { //向上调整,使其满足大根堆的性质 pa = son >> 1; //找到父节点 if (heap[son] <= heap[pa]) break; //如果父节点的值大于等于儿子结点,调整完毕 swap(heap[son], heap[pa]); //向上调整 son = pa; } } //返回堆顶的值,并删除堆顶 int get() { int pa, son, res; res = heap[1]; //存储堆顶的值 heap[1] = heap[heap_size--]; //用最后一个元素覆盖堆顶,并把堆元素个数减一 pa = 1; //向下调整 while (pa * 2 <= heap_size) { son = pa * 2; if (son < heap_size && heap[son + 1] > heap[son]) son++;//找到存在的儿子中最大的一个 if (heap[pa] >= heap[son]) break; //调整完毕 swap(heap[pa], heap[son]);//向下调整 pa = son; } return res;//返回堆顶的值 } int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { int x; cin >> x; put(x); } while (heap_size) { cout << get() << " "; } return 0; }View Code
链接:https://pan.baidu.com/s/1csYxLlghawMtZTALobEJOg?pwd=0000
提取码:0000
标签:应用,int,U7,C++,son,pa,heap,节点,size From: https://www.cnblogs.com/jayxuan/p/18176145