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;
}