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}