堆 (heap)
什么是堆
例 : 计算机CPU调动的排队原则 , 不考虑时序而考虑优先级
- 优先队列 (Priority Queue) : 特殊的”队列” , 取出元素的顺序是按照元素的优先权 (关键字) 大小 , 而不是元素进入队列的先后顺序
操作
主要操作是 : 插入和删除 (最大值或最小值)
用什么数据结构实现优先队列 ?
采用数组实现优先队列
插入 : 元素总是插入尾部
删除 :
①查找最大或最小关键字
②从数组中删去需要移动元素
采用链表实现优先队列
插入 : 元素总时插入链表头部
删除 :
①查找最大或最小关键字
②删去结点
采用有序数组实现优先队列
插入 :
①找到合适的位置 或
②移动元素并插入
删除 : 删去最后一个元素
采用有序链表实现优先队列
插入 :
①找到合适的位置
②插入元素
删除 : 删去首元素或最后元素
是否可以用二叉树?
用二叉查找树 : (不能)
优点 (需求) :
- 查找 : 要查找的结点位置与树的高度有关
- 删除 : 要删除最大或最小值 , 一定在二叉查找树的最左或最右
缺点 :
因为删除的一定是最大或最小值 , 一定在最左或最右 , 删除几次之后树会变歪
如果采用二叉树 , 应更关注插入还是删除 ?
- 树结点顺序怎么安排 ?
- 树结构 ?
显然 , 应该更关注 删除最大值
让最大值在根结点的位置 - 最大堆
用 完全二叉树
优先队列的完全二叉树表示
最大堆和最小堆
堆的抽象数据类型描述
名称 : 最大堆 (MaxHeap)
对象 : 完全二叉树 , 每个结点的元素值不小于其子结点的元素值
操作集 : (最大堆H , 元素 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中最大元素 (高优先级) 主要操作
最大堆的操作
最大堆的创建
创建结构 :
typedef struct HeapStruct *MaxHeap;
struct HeapStruct{
ElementType *Elements; /*存储堆元素的数组*/
int Size; /*堆的当前元素个数*/
int Capacity; /*堆的最大容量*/
}
创建堆 :
MaxHeap Create(int MaxSize){
/*创建容量为MaxSize的空的最大堆*/
MaxHeap H = malloc(sizeof(struct HeapStruct));
/*接下来对结构里的三个分量分别赋值*/
H->Elements = malloc( (MaxSize+1)* sizeof(ElementType));
H->Size = 0;
H->Capacity = MaxSize;
H->Elements[0] = MaxData;
/*定义“哨兵”为大于堆中所有可能元素的值,以便以后更快操作*/
return H;
}
最大堆的插入 O(logN)
void Insert(MaxHeap H, ElementType item){
/*将元素item插入最大堆H,其中H->Elements[0]已经定义为哨兵*/
int i;
if(IsFull(H)){
printf("最大堆已满");
return;
}
i = ++H->Size; /*i指向插入后堆中的最后一个元素的位置,size+1就是最后一个位置*/
for(;H->Elements[i/2]<item; i/=2) /*为了保证有序性与父结点比较*/
H->Elements[i] = H->Elements[i/2]; /*向下过滤结点*/
H->Elements[i] = item; /*将item插入*/
}
for
循环中 , H->Elements[0]
是哨兵元素 , 它不小于堆中的最大元素 , 控制顺环结束
[]
中代表数组下标
当插入的数是所有数中最大的 , 会一直重复 比较 -> 交换
这个过程 , 直到 0号位置的哨兵位置
最大堆的删除
- 取出根结点 (最大值元素) , 同时删除堆的一个结点
(删除的过程相当于是找到根结点替补的过程)
上图中的任务 : 删除元素58
①把 31 移至根
②找出 31 的较大的孩子44 , 交换
③找出 31 的较大的孩子35 , 交换
…(重复这个过程 , 直到31比31的孩子都大)
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){
/*Parent*2 <= H->Size : 判别是否有左儿子*/
Child = Parent*2; /*指向左儿子,有儿子为Parent*2+1*/
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个元素 , 怎么构建最大堆
(将已经存在的N个元素按最大堆的要求存放在一个一维数组中)
方法1 : 插入
通过插入操作 , 将N个元素一个个相继插入到一个初始为空的堆中去 , 时间花费最多为
O(NlogN)
缺点 : 效率不高
方法2 : 线性建立最大堆
在线性时间复杂度下建立最大堆
O(N)
步骤 :
(1) 将N个元素按输入顺序存入 , 先满足完全二叉树的结构特性
(2) 调整各结点位置 , 以满足最大堆的有序特性
(3) 从倒数第一个有儿子的结点开始调整 (把每一个子堆调整好)
(4) 下图的调整顺序 : 87 , 30->72 , 91->83 , 87->43 , 91->66 , 83->66 , 79->91 , 83->79
建堆时 , 最坏情况下需要挪动次数是等于树中各结点的高度和
讨论 : 减堆中某个元素值的操作
将被删除的节点称为A,由堆的性质可知以A为根的子树也是堆,可以仿造堆中删除和添加的算法。为了方便描述我们假定这个堆是最大堆,具体操作如下:
- 将堆中最后一个节点覆盖到A处。
- 比较A与A的根P的大小。如果A>P,则A需要上移,进入步骤3;如果A<P,则A需要下移,进入步骤4。
- 将P和A交换位置,A的根记为P,如果A>P,则执行步骤3,否则结束算法。
- 将当A没有子节点时,结束算法,否则,进入步骤5。
- 将A与最大的子节点M比较,如果A<M,将A与M交换位置,进入步骤4,否则结束算法。
课件
C语言实现 : 堆的定义与操作
typedef struct HNode *Heap; /* 堆的类型定义 */
struct HNode {
ElementType *Data; /* 存储元素的数组 */
int Size; /* 堆中当前元素个数 */
int Capacity; /* 堆的最大容量 */
};
typedef Heap MaxHeap; /* 最大堆 */
typedef Heap MinHeap; /* 最小堆 */
#define MAXDATA 1000 /* 该值应根据具体情况定义为大于堆中所有可能元素的值 */
MaxHeap CreateHeap( int MaxSize )
{ /* 创建容量为MaxSize的空的最大堆 */
MaxHeap H = (MaxHeap)malloc(sizeof(struct HNode));
H->Data = (ElementType *)malloc((MaxSize+1)*sizeof(ElementType));
H->Size = 0;
H->Capacity = MaxSize;
H->Data[0] = MAXDATA; /* 定义"哨兵"为大于堆中所有可能元素的值*/
return H;
}
bool IsFull( MaxHeap H )
{
return (H->Size == H->Capacity);
}
bool Insert( MaxHeap H, ElementType X )
{ /* 将元素X插入最大堆H,其中H->Data[0]已经定义为哨兵 */
int i;
if ( IsFull(H) ) {
printf("最大堆已满");
return false;
}
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插入 */
return true;
}
#define ERROR -1 /* 错误标识应根据具体情况定义为堆中不可能出现的元素值 */
bool IsEmpty( MaxHeap H )
{
return (H->Size == 0);
}
ElementType DeleteMax( MaxHeap H )
{ /* 从最大堆H中取出键值为最大的元素,并删除一个结点 */
int Parent, Child;
ElementType MaxItem, X;
if ( IsEmpty(H) ) {
printf("最大堆已为空");
return ERROR;
}
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;
return MaxItem;
}
/*----------- 建造最大堆 -----------*/
void PercDown( MaxHeap H, int p )
{ /* 下滤:将H中以H->Data[p]为根的子堆调整为最大堆 */
int Parent, Child;
ElementType X;
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];
}
H->Data[Parent] = X;
}
void BuildHeap( MaxHeap H )
{ /* 调整H->Data[]中的元素,使满足最大堆的有序性 */
/* 这里假设所有H->Size个元素已经存在H->Data[]中 */