2.6. 堆
任一节点的关键字是其子树所有节点的最大值 是最大堆
任一节点的关键字是其子树所有节点的最小值 是最小堆
抽象数据结构描述
类型名称: 大顶堆
数据对象集: 完全二叉树
操作集:
MapHeap Creat (int max_size): 创建一个空的最大堆。
Boolean IsFull( MaxHeap H): 判断最大堆是否已经满了。
Insert (MaxHep H): 将元素插入。
IsEmpty(MaxHeap H): 判断最大堆是否为空。
ElementType DeleteMax( MaxHeap H): 删除最大元素。
2.6.1. 堆顺序存储实现
1#include <stdio.h>
2#include <stdlib.h>
3
4#define ElementType int
5
6#define MaxV 9999999
7
8typedef struct HeapStruct *MaxHeap ;
9struct HeapStruct{
10 ElementType *Data;
11 int Size ;
12 int Capacity;
13};
14
15
16MaxHeap CreateHeap(int max_size)
17{
18 MaxHeap h = malloc(sizeof(struct HeapStruct)) ;
19 h->Data= malloc(sizeof( ElementType) * (max_size +1));
20 h->Size= 0 ;
21 h->Capacity = max_size;
22 h->Data[0] = MaxV ;
23 return h ;
24}
25
26int IsHeapFull(MaxHeap h){
27 return h->Capacity == h->Size ;
28}
29int IsEmpty(MaxHeap h){
30 return h->Size==0 ;
31}
32
33void InsertMaxHeap(MaxHeap h, ElementType item){
34 int i ;
35 if (IsHeapFull(h)){
36 printf("heap is full\n");
37 return ;
38 }
39 h->Size +=1;
40 i = h->Size ;
41
42 for (; h->Data[i/2] < item ; i=i/2) {
43 h->Data[i] = h->Data[i/2] ;
44 }
45 h->Data[i] = item ;
46}
47
48ElementType DeleteMax(MaxHeap h){
49 if (IsEmpty(h)){
50 printf("heap is empty\n");
51 return MaxV ;
52 }
53 ElementType maxItem , temp ;
54 int parent , child ;
55
56 maxItem = h->Data[1];
57 temp = h->Data[h->Size] ;
58 h->Size -=1;
59 for ( parent = 1; 2* parent <= h->Size ; parent = child ) {
60 child = 2 * parent ;
61 if (child !=h->Size && h->Data[child] < h->Data[child+1]){
62 child +=1 ;
63 }
64 if (temp >= h->Data[child]){
65 break;
66 }else{
67 h->Data[parent] = h->Data[child] ;
68 }
69 }
70 h->Data[parent] = temp;
71 return maxItem ;
72}
73
74void PrintMaxHeap(MaxHeap h){
75 int j ;
76 for (int i = 1; i <=h->Size ; i=i*2) {
77 j = i ;
78 while (j<i*2 && j<=h->Size){
79 printf("%d ",h->Data[j]);
80 j+=1;
81 }
82 printf("\n");
83
84 }
85}
86//void PercDown( MaxHeap H, int p){
87//
88//}
89//
90//void BuildMaxHeap(MaxHeap H){
91//
92//}
93
94int main(){
95 MaxHeap h = CreateHeap(100);
96 InsertMaxHeap(h,1);
97 InsertMaxHeap(h,2);
98 InsertMaxHeap(h,3);
99 InsertMaxHeap(h,4);
100 InsertMaxHeap(h,5);
101 InsertMaxHeap(h,6);
102 InsertMaxHeap(h,7);
103 InsertMaxHeap(h,8);
104 PrintMaxHeap(h) ;
105 printf("******\n");
106 DeleteMax(h);
107 PrintMaxHeap(h) ;
108 printf("\n");
109}