数据结构|堆——堆的操作集、建造堆及打印堆中的路径数据结构|堆

1 堆的类型定义

typedef struct HeapStruct *Heap/*堆的类型定义*/ struct HeapStruct { ElementType *Data; /*存储元素的数组*/ int Size；/*堆的当前元素个数*/ int Capacity; /*堆的最大容量*/ }; typedef Heap MaxHeap; /*最大堆*/ typedef Heap MinHeap; /*最小堆*/

2 创建容量为MaxSize的空的最大堆

#define MaxData 10000/* 该值应根据具体情况定义为大于堆中所有可能元素的值 */MaxHeap CreateHeap( int MaxSize){ MaxHeap H = (Maxheap)malloc(sizeof(struct HeapStruct)); H->Data = https://www.it610.com/article/(ElementType *)malloc((MaxSize+1)*sizeof(ElementType)); H->Size = 0; H->Capacity = MaxSize; H->Data[0] = MaxData; /* 定义"哨兵"为大于堆中所有可能元素的值*/return H; }

3 最大堆的插入（T(N) = O（logN））

bool IsFull( MaxHeap H){ return (H->Size == H->Capacity); }bool Insert(MaxHeap H , ElementType X){ /* 将元素X插入最大堆H，其中H->Data[0]已经定义为哨兵 */ int i; /*i为要插入的数组位置下表*/if(IsFull(H)){ printf("最大堆已满"); return false; } i = ++H->Size; /* i指向插入后堆中的最后一个元素的位置 */ for(; H->Data[i/2]Data[i] = H->Data[i/2]; /* 上滤X */ H->Data[i] = item; /* 将X插入 */ return true; }

4 最大堆的删除（T(N) = O（logN））

#define ERROR-1; /* 错误标识应根据具体情况定义为堆中不可能出现的元素值 */bool IsEmpty(MaxHeap H){ return(H->Size ==0); }ElementType DeleteMax( MaxHeap H){ ElemetType MaxItem,Temp; int Parent, Child; MaxItem = H->Data[1]; Temp = H->Data[H->Size--]; for(Parent = 1; H->Size >= 2*Parent; ){ /*从根节点开始向上过滤下层结点,主要目的是要找Temp要插入的位置Parent*/ Child = 2*Parent; /*先默认为左儿子，因为根据前面判断条件它可能没有右儿子*/ if((H->Size > Child) && (H->Data[Child]Data[Child+1]))/*如果有右儿子并且右儿子比左儿子大*/ Child++; if(H->Data[Child]>Temp) {/*注意这里是和Temp比较，不是H->Data[Parent]*/ H->Data[Parent] = H->Data[Child]; Parent = Child; /*可以放到for语句里*/ } else break; } H->Data[Parent] = Temp ; return MaxItem ; }

5 最大堆的建立（T(N) = O（N））两种方法：

方法1：通过插入操作，将N个元素一个个相继插入到一个初始为空的堆中去，时间复杂度为O（NlogN）
方法2：在线性时间复杂度上建立堆。O（N）
（1）将N个元素按输入顺序存入，先满足完全二叉树的结构特性。
（2）调整各结点位置，以满足最大堆的有序特性。

void BuildHeap( MaxHeap H ) {/* 这里假设传入的最大堆是个数是空的 */ int i; for(i=1; i<=N; i++){/* 这里假设元素个数N不大于MaxSize*/ scanf("%d",&H->Data[i])； H->Size++；return H; } /* 调整H->Data[]中的元素，使满足最大堆的有序性*/ /* 从最后一个结点的父节点开始，到根结点1 */ for( i = H->Size/2; i>0; i-- ) PercDown( H, i ); }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]Data[Child+1]) ) Child++; /* Child指向左右子结点的较大者 */ if( X >= H->Data[Child] ) break; /* 找到了合适位置 */ else/* 下滤X */ H->Data[Parent] = H->Data[Child]; } H->Data[Parent] = X; }

6 打印堆中的路径 【数据结构|堆——堆的操作集、建造堆及打印堆中的路径】

文章图片

#include #include #define bool char #define ture 1 #define false 0 #define MinData -10001 #define MaxSize 10001 typedef int ElementType; typedef struct HeapStruct *MinHeap; /*堆的类型定义*/ struct HeapStruct { ElementType *Data; /*存储元素的数组*/ int Size; /*堆的当前元素个数*/ int Capacity; /*堆的最大容量*/ }; MinHeap CreateHeap( int Size){ MinHeap H = (MinHeap)malloc(sizeof(struct HeapStruct)); H->Data = https://www.it610.com/article/(ElementType *)malloc((Size+1)*sizeof(ElementType )); H->Size = 0; H->Capacity = MaxSize; H->Data[0] = MinData ; /* 定义"哨兵"为小于堆中所有可能元素的值*/ return H; }bool IsFull( MinHeap H){ return (H->Size == H->Capacity); }bool Insert(MinHeap H,ElementType X){ /* 将元素X插入最大堆H，其中H->Data[0]已经定义为哨兵 */ int i; /*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 ture; } int main(){ int n,m,x,i,j; scanf("%d%d",&n,&m); MinHeap H = CreateHeap(MaxSize ); /*堆初始化*/ for(i=0; i=1; j/=2){ printf("%d",H->Data[j]); } printf("\n"); } return 0; }