堆的定义：![52aadec278a8887e4b06664609dc4332.png]()
堆的由来：要从优先队列说起，优先队列的定义：一般的队列取出的值是先进先出，是按入队顺序去出的。那么优先队列则是按照元素的优先权的大小，比如总是取出一组数据中的最大数。那么优先队列如何实现呢？？可以通过数组和链表实现，但是时间复杂度很高。如下：![d4f71b9e5f0eb1260f98e0f8cb0a9dc7.png]()
最好的办法就是完全二叉树来实现优先队列，我们知道完全二叉树最好的存储方式就是数组，而不是链表，可以说堆是集结了完全二叉树和搜索二叉树的特点。
堆的主要函数有如下：![9930258875818944b2e6ce20c65eb13b.png]()
其中最重要的函数就是插入和删除函数，本来我想自己给这几个函数写出来，写一个自己的算法堆，时间有限，直接放上课程的标准代码，以后有时间我在自己去写出来。
堆的由来：要从优先队列说起，优先队列的定义：一般的队列取出的值是先进先出，是按入队顺序去出的。那么优先队列则是按照元素的优先权的大小，比如总是取出一组数据中的最大数。那么优先队列如何实现呢？？可以通过数组和链表实现，但是时间复杂度很高。如下：
最好的办法就是完全二叉树来实现优先队列，我们知道完全二叉树最好的存储方式就是数组，而不是链表，可以说堆是集结了完全二叉树和搜索二叉树的特点。堆的主要函数有如下：
其中最重要的函数就是插入和删除函数，本来我想自己给这几个函数写出来，写一个自己的算法堆，时间有限，直接放上课程的标准代码，以后有时间我在自己去写出来。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 |
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[]中 */ int i; /* 从最后一个结点的父节点开始，到根结点1 */ for( i = H->Size/2; i>0; i-- ) PercDown( H, i ); } |
