5.1 堆(heap)
5.1.1 什么是堆
优先队列(Priority Queue)：特殊的"队列"，取出元素的顺序是依照元素的优先权(关键字)大小，而不是元素进入队列的先后顺序
-
网络异常，图片无法展示|
- 是否可以采用二叉树存储结构？
- 二叉搜索树？
- 如果采用二叉树结构，应更关注插入还是删除？
- 树结点顺序怎么安排？
- 树结构怎么样？
- 优先队列的完全二叉树表示
-
网络异常，图片无法展示|
堆的两个特性
结构性：用数组表示的完全二叉树;
有序性：任一结点的关键字是其子树所有结点的最大值(或最小值)
"最大堆(MaxHeap)"，也称"大顶堆"：最大值
"最小堆(MinHeap)"，也称"小顶堆"：最小值
通俗的来说就是最大堆的上面的那个要比连接下面两个都要大。最小堆则相反，最上面那个要比连接下面两个都要小。同时需要是完全二叉树
注意：从根结点到任意结点路径上结点系列的有序性！
-
网络异常，图片无法展示|
堆的抽象数据类型描述
类型名称：最大堆(MaxHeap)
数据对象集：完全二叉树，每个结点的元素值不小于其子结点的元素值
操作集：最大堆H属于MAaxHeap,元素item属于ElementType，主要操作有：
1.MaxHeap Create(int MaxSize)：创建一个空的最大堆
2.Boolean IsFull(MaxHeap H)：判断最大堆H是否已满
3.Insert(MaxHeap H,ElementType item)：将元素item插入最大堆H
4.Boolean IsEmpty(MaxHeap H):判断最大堆H是否为空
5.ElementType DeleteMax(MaxHeap H)：返回H中最大元素(高优先级)
5.1.2 堆的插入
最大堆的创建
typedefstructHeapStruct*MaxHeap;
structHeapStruct{
ElementTye*Elements;//存储堆元素的数组
intSize;//堆的当前元素个数
intCapacity;//堆的最大容量
};
MaxHeapCreate(intMaxSize)
{
//创建容量为MaxSize的空的最大堆
MaxHeapH=malloc(sizeof(structHeapStruct));
H->Elements=malloc((Maxsize+1)*sizeof(ElementType));//Maxsize+1是希望申请的容量
H->Size=0;
H->Capacity=MaxSize;
H->Elements[0] =MaxSize;
H->Elements[0] =MaxData;
//定义"哨兵"为大于堆中所有可能元素的值，便于以后更快操作
returnH;
}
最大堆的插入
-
网络异常，图片无法展示|
-
网络异常，图片无法展示|
-
网络异常，图片无法展示|
- 如果在底下插入的数值比上面大就沿着线路一路换位置，直到上面没有在比插入的大了为止
- 算法的实现如下:将新增结点插入到从其父结点到根结点的有序序列中
voidInsert(MaxheapH,ElementTypeitem)
{
//将元素item插入最大堆H,其中H->Elements[0]已经定义为哨兵
inti;
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)
-
网络异常，图片无法展示|
问题：“哨兵”是在创建堆(Create函数）时设置的：H->Elements[0]=MaxData;
答案：这是对的
5.1.3 堆的删除
最大堆的删除
- 取出根结点(最大值)元素，同时删除堆的一个结点
-
网络异常，图片无法展示|
-
网络异常，图片无法展示|
- 时间复杂度就等于树的高度
- 删除MaxHeap程序实现：
ElementTypeDeleteMax(MaxHeapH)
{
//从最大堆H中取出键值为最大的元素，并删除一个结点
intParent,Child;
ElementTypeMaxItem,temp;
if( IsEmpty(H)){
printf("最大堆已为空");
return;
}
MaxItem=H->Elements[1];//取出根结点最大值，保存起来，最后是要return出去的
//temp = H->Elements[H->Size--];
for(Parent=1;Parent*2<=H->Size;Parent=Child){//Parent指示我将来要换的位置，退出循环就说明了我们要的位置找到了
Child=Parent*2;//Child指向左儿子
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;
returnMaxItem;
}
在完全二叉树里面，i代表一个节点，它的左儿子在2i,右儿子在2i+1
如果左儿子2i已经超出Size的范围，说明左儿子已经在堆栈外面了，那就说明它没左儿子
Parent*2<=H->Size是判别它有没有左儿子，如果没有左儿子那右儿子肯定也没有那就退出循环了
Child!=H->Size：Child指向左儿子意味左儿子是最后一个元素了，那就意味着没有右儿子了。实际上这个就相当于判别有没有右儿子
- 问题：有个堆其元素在数组中的序列为：58，25，44，18，10，26，20，12。如果调用DeleteMax函数删除最大值元素，请猜猜看：程序中的for循环刚退出时变量parent的值是多少？
是6
5.1.4 堆的建立
堆的一个应用：堆排序--需要先建堆
最大堆的建立
建立最大堆：将已经存在的N个元素按最大堆的要求存放在一个一维数组中
方法1：通过插入操作，将N个元素一个个相继插入到一个初始为空的堆中去，其时间代价最大为O(NlogN)
每次插入 它的时间复杂性是log2N
总共循环N遍，所以整个时间复杂性是Nlog2N
上方这个方法1的效率是不够的，我们可以有更好的方法
方法2：在线性时间复杂度下建立最大堆.
(1)将N个元素按输入顺序存入，先满足完全二叉树的结构特性
(2)调整各结点位置，以满足最大堆的有序特性
问：建堆时，最坏情况下需要挪动元素次数是等于树中各结点的高度和。问：对于元素个数为12的堆，其各结点的高度之和是多少？10
小测验：堆
C语言代码：堆的定义和操作
typedefstructHNode*Heap; /* 堆的类型定义 */
structHNode {
ElementType*Data; /* 存储元素的数组 */
intSize; /* 堆中当前元素个数 */
intCapacity; /* 堆的最大容量 */
};
typedefHeapMaxHeap; /* 最大堆 */
typedefHeapMinHeap; /* 最小堆 */
#define MAXDATA 1000 /* 该值应根据具体情况定义为大于堆中所有可能元素的值 */
MaxHeapCreateHeap( intMaxSize )
{ /* 创建容量为MaxSize的空的最大堆 */
MaxHeapH= (MaxHeap)malloc(sizeof(structHNode));
H->Data= (ElementType*)malloc((MaxSize+1)*sizeof(ElementType));
H->Size=0;
H->Capacity=MaxSize;
H->Data[0] =MAXDATA; /* 定义"哨兵"为大于堆中所有可能元素的值*/
returnH;
}
boolIsFull( MaxHeapH )
{
return (H->Size==H->Capacity);
}
boolInsert( MaxHeapH, ElementTypeX )
{ /* 将元素X插入最大堆H，其中H->Data[0]已经定义为哨兵 */
inti;
if ( IsFull(H) ) {
printf("最大堆已满");
returnfalse;
}
i=++H->Size; /* i指向插入后堆中的最后一个元素的位置 */
for ( ; H->Data[i/2] <X; i/=2 )
H->Data[i] =H->Data[i/2]; /* 上滤X */
H->Data[i] =X; /* 将X插入 */
returntrue;
}
#define ERROR -1 /* 错误标识应根据具体情况定义为堆中不可能出现的元素值 */
boolIsEmpty( MaxHeapH )
{
return (H->Size==0);
}
ElementTypeDeleteMax( MaxHeapH )
{ /* 从最大堆H中取出键值为最大的元素，并删除一个结点 */
intParent, Child;
ElementTypeMaxItem, X;
if ( IsEmpty(H) ) {
printf("最大堆已为空");
returnERROR;
}
MaxItem=H->Data[1]; /* 取出根结点存放的最大值 */
/* 用最大堆中最后一个元素从根结点开始向上过滤下层结点 */
X=H->Data[H->Size--]; /* 注意当前堆的规模要减小 */
for( Parent=1; Parent*2<=H->Size; Parent=Child ) {
Child=Parent*2;
if( (Child!=H->Size) && (H->Data[Child]<H->Data[Child+1]) )
Child++; /* Child指向左右子结点的较大者 */
if( X>=H->Data[Child] ) break; /* 找到了合适位置 */
else /* 下滤X */
H->Data[Parent] =H->Data[Child];
}
H->Data[Parent] =X;
returnMaxItem;
}
/*----------- 建造最大堆 -----------*/
voidPercDown( MaxHeapH, intp )
{ /* 下滤：将H中以H->Data[p]为根的子堆调整为最大堆 */
intParent, Child;
ElementTypeX;
X=H->Data[p]; /* 取出根结点存放的值 */
for( Parent=p; Parent*2<=H->Size; Parent=Child ) {
Child=Parent*2;
if( (Child!=H->Size) && (H->Data[Child]<H->Data[Child+1]) )
Child++; /* Child指向左右子结点的较大者 */
if( X>=H->Data[Child] ) break; /* 找到了合适位置 */
else /* 下滤X */
H->Data[Parent] =H->Data[Child];
}
