我是靠谱客的博主 怕黑小鸭子，最近开发中收集的这篇文章主要介绍堆（大小顶堆）的概念以及基本操作（建堆、增、删、堆排序）——附带完整代码以及示例1 堆2 基本操作3 完整示例，觉得挺不错的，现在分享给大家，希望可以做个参考。
概述
文章目录
- 1 堆
- 2 基本操作
- 2.1 建堆
- 2.1.1存储结构
- 2.1.2 自上而下调整
- 2.1.3 创建堆
- 2.2 删除堆顶元素
- 2.3 增加元素
- 2.3.1 自下往上调整
- 2.3.2 增加一个元素
- 2.4 堆排序
- 3 完整示例
- 3.1 大顶堆
- 3.2 小顶堆（实现哈夫曼树）
1 堆
- 概念：一颗完全二叉树，树中的每个结点的值不大于（或不小于）其左右孩子的值。
- 大顶堆：父结点的值大于或等于孩子结点的值，每个结点值都以它为根结点的子树的最大值；
- 小顶堆：父结点的值小于或等于孩子结点的值，每个结点值都以它为根结点的子树最小的值。
- 堆一般用优先队列，优先队列默认使用大顶堆，下面的讲解以大顶堆为主，另外当大小顶堆操作不同时，附带小顶堆实现代码。
2 基本操作
2.1 建堆
- 规则：从最后一个位置开始，从右到左，从下到上。用结点x与结点x所有孩子结点比较，如果孩子结点y有大于x的值，就交换x和y为位置，交换后，让x继续与原来y结点的所有孩子比较，直到现在位置结点x的所有孩子结点值都比它小，或者没有孩子结点为止。
2.1.1存储结构
- 数组存储完全二叉树，第一个结点序号从1开始，数组i号位的左孩子结点就是（2 * i）号位，右孩子则是(2 * i + 1)号位；
const int MAXN = 110;
int heap[MAXN]; //第一个结点存储在数组中的一号位
int n;//元素个数
2.1.2 自上而下调整
- 大顶堆
//对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[j], heap[i]);//交换最大权值孩子和欲调整结点
i = j;
j = i * 2;
}else{
break;//孩子中权值均比欲调整结点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[j], heap[i]);
i = j;
j = i * 2;
}else{
break;
}
}
}
2.1.3 创建堆
//创建堆
void createHeap(){
//序列元素个数为n的非叶子结点为[1,n/2],n/2向下取整
//倒着枚举是因为，每次调整完一个结点后，当前子树中权值最大的结点就会处在根结点的位置
for (int i = n / 2; i >= 1; --i)
{
downAdjust(i, n);
}//结点按层序存储在数组中
}
2.2 删除堆顶元素
- 用最后一个元素覆盖堆顶元素，对根结点进行调整
//删除堆顶元素
void deleteTop(){
heap[1] = heap[n--];
downAdjust(1,n);
}
2.3 增加元素
2.3.1 自下往上调整
- 大顶堆
//向上调整
//一般low为1，high为欲调整的数组元素下标
void upAdjust(int low, int high){
int i = high, j = i / 2;
while(j >= low){//父结点在[low,high]中
if(heap[j] < heap[i]){
swap(heap[j], heap[i]);
i = j;
j = i / 2;
}else{
break;
}
}
}
- 小顶堆
void upAdjust(int low, int high){
int i = high, j = i / 2;
while(j >= low){
if(heap[j] > heap[i]){
swap(heap[j], heap[i]);
i = j;
j = i / 2;
}else{
break;
}
}
}
2.3.2 增加一个元素
//添加元素
//放在完全二叉树的最后一个结点后面
void Insert(int x){
heap[++n] = x;
upAdjust(1,n);
}
2.4 堆排序
//堆排序
void heapSort(){
createHeap();//建堆
for (int i = n; i > 1; --i)//倒着枚举，直到堆中 只有一个元素
{
swap(heap[i], heap[1]);
downAdjust(1, i - 1);//调整堆顶
}
}
3 完整示例
3.1 大顶堆
#include <cstdio>
#include <algorithm>
using std::swap;
const int MAXN = 110;
int heap[MAXN]= {0, 85, 55, 82, 57, 68, 92, 99, 98, 66, 56}; //第一个结点存储在数组中的一号位
int n = 10;
//对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[j], heap[i]);//交换最大权值孩子和欲调整结点
i = j;
j = i * 2;
}else{
break;//孩子中权值均比欲调整结点i小，调整结束
}
}
}
//创建堆
void createHeap(){
//序列元素个数为n的非叶子结点为[1,n/2],n/2向下取整
//倒着枚举是因为，每次调整完一个结点后，当前子树中权值最大的结点就会处在根结点的位置
for (int i = n / 2; i >= 1; --i)
{
downAdjust(i, n);
}//结点按层序存储在数组中
}
//删除堆顶元素
void deleteTop(){
heap[1] = heap[n--];
downAdjust(1,n);
}
//向上调整
//一般low为1，high为欲调整的数组元素下标
void upAdjust(int low, int high){
int i = high, j = i / 2;
while(j >= low){//父结点在[low,high]中
if(heap[j] < heap[i]){
swap(heap[j], heap[i]);
i = j;
j = i / 2;
}else{
break;
}
}
}
//添加元素
//放在完全二叉树的最后一个结点后面
void Insert(int x){
heap[++n] = x;
upAdjust(1,n);
}
//堆排序
void heapSort(){
createHeap();//建堆
for (int i = n; i > 1; --i)//倒着枚举，直到堆中 只有一个元素
{
swap(heap[i], heap[1]);
downAdjust(1, i - 1);//调整堆顶
}
}
int main(int argc, char const *argv[])
{
createHeap();
//输出：99 98 92 66 68 85 82 57 55 56
// heapSort();
//输出：55 56 57 66 68 82 85 92 98 99
//deleteTop();
//输出：82 55 99 57 68 92 56 98 66
Insert(100);
//输出：100 99 92 66 98 85 82 57 55 56 68
for (int i = 1; i <= n; ++i)
{
printf("%d ", heap[i]);
}
return 0;
}
3.2 小顶堆（实现哈夫曼树）
#include <cstdio>
#include <algorithm>
using std::swap;
const int MAXN = 20010;
long long heap[MAXN];
int n;
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[j], heap[i]);
i = j;
j = i * 2;
}else{
break;
}
}
}
void createHeap(){
for (int i = n / 2; i >= 1; --i)
{
downAdjust(i, n);
}
}
void deleteTop(){
heap[1] = heap[n--];
downAdjust(1, n);
}
void upAdjust(int low, int high){
int i = high, j = i / 2;
while(j >= low){
if(heap[j] > heap[i]){
swap(heap[j], heap[i]);
i = j;
j = i / 2;
}else{
break;
}
}
}
void Insert(int x){
heap[++n] = x;
upAdjust(1, n);
}
int main(int argc, char const *argv[])
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
scanf("%lld", &heap[i]);
}
createHeap();
long long ans = 0;
long long x, y;
while(n > 1){
x = heap[1];
deleteTop();
y = heap[1];
deleteTop();
Insert(x + y);
ans += x + y;
}
printf("%lldn", ans);
return 0;
}
/*
Input:
3
1 2 9
Output:
15
*/
最后
以上就是怕黑小鸭子为你收集整理的堆（大小顶堆）的概念以及基本操作（建堆、增、删、堆排序）——附带完整代码以及示例1 堆2 基本操作3 完整示例的全部内容，希望文章能够帮你解决堆（大小顶堆）的概念以及基本操作（建堆、增、删、堆排序）——附带完整代码以及示例1 堆2 基本操作3 完整示例所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复