C/C++教程
堆结构c/c++
本文主要是介绍堆结构c/c++，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
c语言堆
一、定义：
“优先队列” （Priority Queue）是特殊的“队列”，从堆中取出元素的顺序是依照元素的优先权（关键字）大小，而不是元素进入队列的先后顺序。采用完全二叉树存储的优先队列 称为堆（Heap）。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nSQ3piUZ-1645324036393)(C:\Users\Π\AppData\Roaming\Typora\typora-user-images\image-20211130201925755.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Jribiddp-1645324036394)(C:\Users\Π\AppData\Roaming\Typora\typora-user-images\image-20211130202336664.png)]
类型名称：最大堆（MaxHeap）
数据对象集：一个有N>0个元素的最大堆H是一棵完全二叉树，每个结点上的元素值不小于其子结点元素的值。
操作集：对于任意最多有MaxSize个元素的最大堆H MaxHeap，元素item ElementType，主要操作有：
MaxHeap Create( int MaxSize )//创建一个空的最大堆。 Boolean IsFull( MaxHeap H )//判断最大堆H是否已满。 Insert( MaxHeap H, ElementType item )//将元素item插入最大堆H。 Boolean IsEmpty( MaxHeap H )//判断最大堆H是否为空。 ElementType DeleteMax( MaxHeap H )//返回H中最大元素(高优先级)
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-51jUPXaO-1645324036394)(C:\Users\Π\AppData\Roaming\Typora\typora-user-images\image-20211130202438933.png)]
二、最大堆的操作
最大堆的创建：
struct HeapStruct {
ElementType *Elements; /* 存储堆元素的数组 */
int Size; /* 堆的当前元素个数 */
int Capacity; /* 堆的最大容量 */
};
typedef struct HeapStruct *MaxHeap;
MaxHeap Create( int MaxSize )
{ /* 创建容量为MaxSize的空的最大堆 */
MaxHeap H =(MaxHeap)malloc( sizeof( struct HeapStruct ) );
H->Elements =(MaxHeap)malloc( (MaxSize+1) * sizeof(ElementType));
//从1开始，0作为哨兵
H->Size = 0;
H->Capacity = MaxSize;
H->Elements[0] = MaxData;
/* 定义“哨兵”为大于堆中所有可能元素的值，便于以后更快操作 */
return H;
}
//把MaxData换成小于堆中所有元素的MinData，同样适用于创建最小堆。
最大堆的插入：
void Insert( MaxHeap H, ElementType item )
{ /* 将元素item 插入最大堆H，其中H->Elements[0]已经定义为哨兵 */
int i;
if ( IsFull(H) ) {
printf("最大堆已满");
return;
}
i = ++H->Size; /* i指向插入后堆中的最后一个元素的位置 */
for ( ; H->Elements[i/2] < item; i/=2 )
H->Elements[i] = H->Elements[i/2]; /* 向下过滤结点 */
H->Elements[i] = item; /* 将item 插入 在数据大于所有节点数据时哨兵起效*/
}
//T(N)=O(logN)
最大堆的删除 删除最大值:
ElementType DeleteMax( MaxHeap H )
{ /* 从最大堆H中取出键值为最大的元素，并删除一个结点 */
int Parent, Child;
ElementType MaxItem, temp;
if ( IsEmpty(H) ) {
printf("最大堆已为空");
return;
}
MaxItem = H->Elements[1]; /* 取出根结点最大值 */
/* 用最大堆中最后一个元素从根结点开始向上过滤下层结点 */
temp = H->Elements[H->Size--];
for( Parent=1; Parent*2<=H->Size; Parent=Child ) {
Child = Parent * 2;
if( (Child!= H->Size) &&
(H->Elements[Child] < H->Elements[Child+1]) )
Child++; /* Child指向左右子结点的较大者 */
if( temp >= H->Elements[Child] ) break;//退出的窗口
else /* 移动temp元素到下一层 */
H->Elements[Parent] = H->Elements[Child];
}
H->Elements[Parent] = temp;
return MaxItem;
最大堆的建立：“建立最大堆”是指如何将已经存在的N个元素按最大堆的要求存放在一个一维数组中。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lboKjScr-1645324036395)(C:\Users\Π\AppData\Roaming\Typora\typora-user-images\image-20211130203408548.png)]
MaxHeap BuildMaxHeap( MaxHeap H )
{ /* 这里假设所有H->Size个元素已经存在H->Elements[]中 */
/* 本函数将H->Elements[]中的元素调整，通过从最小的每个子树开始往上，逐步满足要求，使满足最大堆的有序性 */
int Parent, Child, i;
ElementType temp;
for( i = H->Size/2; i>0; i-- ){ /*从最后一个结点的父结点开始 */
temp = H->Elements[i];
for( Parent=i; Parent*2<=H->Size; Parent=Child ) {
/* 向下过滤 */
Child = Parent * 2;
if( (Child!= H->Size) &&
(H->Elements[Child] < H->Elements[Child+1]) )
Child++; /* Child指向左右子结点的较大者 */
if( temp >= H->Elements[Child] ) break;
else /* 移动temp元素到下一层 */
H->Elements[Parent] = H->Elements[Child];
} /* 结束内部for循环对以H->Elements[i]为根的子树的调整 */
H->Elements[Parent] = temp;
}
return H;
}
c++模板
类模板
//堆结构
template <typename T>
class CMyHeap
{
//数据域
T* pBuff;
size_t len;
size_t MaxSize;
public:
CMyHeap();
~CMyHeap();
//拷贝构造
CMyHeap(CMyHeap const& heap);
void clear();
//添加删除初始化
void appEndNode(T const& srcData);
void deleteNode();
void initHeap(T arr[], size_t srcLen);
T * out(){ return pBuff; } //返回的是地址
};
/*
堆的初始化
1、加入数组的所有数据
2、依次调整，根据删除逻辑调整，从最后一个有子树的结点开始调整
*/
template<typename T>
void CMyHeap<T>::initHeap(T arr[], size_t srcLen)
{
//1、清空容器
clear();
//2、插入内容为空 退出
if (srcLen == 0)
return;
//3、数据入堆
len = MaxSize = srcLen;
pBuff = new T[MaxSize];
for (int i = 0; i < len; ++i)
pBuff[i] = arr[i];
//4、调整位置
for (int i = (int)((len - 2) >> 1); i >= 0; --i)//要调整的次数
{
//4.1、保存信息
int index = i;
T tempData = pBuff[index];//保存的值
//4.2、正式调整
while (true)
{
//4.1、获取左右子树的下标
size_t left = 2 * index + 1;
size_t right = 2 * index + 2;
//4.2、判断有无子树
if (left > (len - 1))//比较到底了
break;
//存在子树
//4.3、设置一个标记，表示左右谁更大
bool isLeft = true;
if (right < len)//右子树存在
{
if (pBuff[left] < pBuff[right])//右子树更大
isLeft = false;//修改标记
}
//4.4、根节点与较大者比较
if (isLeft)
{
//和左子树比较
if (tempData < pBuff[left])
{
//左子树上位
pBuff[index] = pBuff[left];
index = left;//下标更新
}
else
break;//找到了位置 退出
}
else
{
//和右子树比较 false
if (tempData < pBuff[right])
{
//右子树上位
pBuff[index] = pBuff[right];
index = right;//下标更新
}
else
break;//找到了位置 退出
}
}
//5、循环结束 到叶节点了 到对应位置
pBuff[index] = tempData;
}
}
/*
堆的删除逻辑
1、每次删除都删根节点
2、把最后一个结点覆盖到根节点，元素减一
3、调整位置以满足堆特性
*/
template<typename T>
void CMyHeap<T>::deleteNode()
{
//1、空堆
if (len == 0)
return;
//2、元素大于1 最后一个结点覆盖到根节点
if (len > 1)
pBuff[0] = pBuff[len - 1];
len--;
//3、保存信息 下标和值
int index = 0;
T tempData = pBuff[index];
//4、开始调整
while (true)
{
//4.1、获取左右子树的下标
size_t left = 2 * index + 1;
size_t right = 2 * index + 2;
//4.2、判断有无子树
if (left > (len - 1))//比较到底了
break;
//否则存在子树
//4.3、设置一个标记，表示左右谁更大
bool isLeft = true;
if (right < len)//右子树存在
{
if (pBuff[left] < pBuff[right])//右子树更大
isLeft = false;//修改标记
}
//4.4、根节点与较大者比较
if (isLeft)
{
//和左子树比较
if (tempData < pBuff[left])
{
//左子树上位
pBuff[index] = pBuff[left];
index = left;//下标更新
}
else
break;//找到了位置 退出
}
else
{
//和右子树比较 false
if (tempData < pBuff[right])
{
//右子树上位
pBuff[index] = pBuff[right];
index = right;//下标更新
}
else
break;//找到了位置 退出
}
}
//5、循环结束 到叶节点了 到对应位置
pBuff[index] = tempData;
}
template<typename T>
void CMyHeap<T>::appEndNode(T const& srcData)
{
//1、扩容
if (len >= MaxSize)
{
//1.1、半倍扩容
MaxSize += ((MaxSize >> 1) > 1 ? (MaxSize >> 1) : 1);
T * pTemp = new T[MaxSize];
//1.2、复制转移
for (size_t i = 0; i < len; ++i)
{
pTemp[i] = pBuff[i];
}
//1.3、过河拆桥
if (pBuff)
delete[] pBuff;
pBuff = pTemp;
}
//扩容完成，插入数据
pBuff[len++] = srcData;
//2、记录信息 - 下标与数值
int tempIndex = len - 1;
T tempData = pBuff[tempIndex];
//3、调整位置
while (tempIndex)//=0 找到根节点
{
int parentIndex = (tempIndex - 1) >> 1;//右移除2到父节点
if (pBuff[parentIndex] < tempData)//父节点比子结点小 数据下移
pBuff[tempIndex] = pBuff[parentIndex];
else
break;
//循环的步长
tempIndex = parentIndex;
}
//出循环了 要不找到了合适的位置 要不就找到根节点了，此时根节点作为哨兵
//4、不管是什么原因 都需要插入的最后一步 放入数据
pBuff[tempIndex] = tempData;
}
template<typename T>
void CMyHeap<T>::clear()
{
if (pBuff)
delete[] pBuff;
pBuff = nullptr;
len = MaxSize = 0;
}
template<typename T>
CMyHeap<T>::CMyHeap(CMyHeap const& heap)
{
this->pBuff = new T[heap.MaxSize];
MaxSize = heap.MaxSize;
len = heap.len;
for (int i = 0; i < len; ++i)
{
pBuff[i] = heap.pBuff[i];
}
}
template<typename T>
CMyHeap<T>::~CMyHeap()
{
clear();
}
template<typename T>
CMyHeap<T>::CMyHeap()
{
pBuff = nullptr;
len = MaxSize = 0;
}
主函数调试
#include <iostream>
#include <string>
#include "CMyHeap.hpp"
using namespace std;
int main()
{
CMyHeap<int> mh;
mh.appEndNode(1);
mh.appEndNode(2);
mh.appEndNode(3);
mh.appEndNode(1);
mh.deleteNode();
int arr[]{1, 2, 3, 4, 5};
mh.initHeap(arr, 5);
CMyHeap<int> mh2(mh);
cout << mh.out() << endl;
//system("pause");
return 0;
}
主函数调试
#include <iostream>
#include <string>
#include "CMyHeap.hpp"
using namespace std;
int main()
{
CMyHeap<int> mh;
mh.appEndNode(1);
mh.appEndNode(2);
mh.appEndNode(3);
mh.appEndNode(1);
mh.deleteNode();
int arr[]{1, 2, 3, 4, 5};
mh.initHeap(arr, 5);
CMyHeap<int> mh2(mh);
cout << mh.out() << endl;
//system("pause");
return 0;
}
这篇关于堆结构c/c++的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
增量更新怎么做？-icode9专业技术文章分享11-23
-
压缩包加密方案有哪些？-icode9专业技术文章分享11-23
-
用shell怎么写一个开机时自动同步远程仓库的代码？-icode9专业技术文章分享11-23
-
webman可以同步自己的仓库吗？-icode9专业技术文章分享11-23
-
在 Webman 中怎么判断是否有某命令进程正在运行？-icode9专业技术文章分享11-23
-
如何重置new Swiper?-icode9专业技术文章分享11-23
-
oss直传有什么好处？-icode9专业技术文章分享11-23
-
如何将oss直传封装成一个组件在其他页面调用时都可以使用？-icode9专业技术文章分享11-23
-
怎么使用laravel 11在代码里获取路由列表？-icode9专业技术文章分享11-23
-
怎么实现ansible playbook 备份代码中命名包含时间戳功能？-icode9专业技术文章分享11-22
-
ansible 的archive 参数是什么意思？-icode9专业技术文章分享11-22
-
ansible 中怎么只用archive 排除某个目录？-icode9专业技术文章分享11-22
-
exclude_path参数是什么作用？-icode9专业技术文章分享11-22
-
微信开放平台第三方平台什么时候调用数据预拉取和数据周期性更新接口？-icode9专业技术文章分享11-22
-
uniapp 实现聊天消息会话的列表功能怎么实现？-icode9专业技术文章分享11-22
栏目导航
