6月10日数据结构——堆

堆的建立和输出

#include<stdio.h>
#include<stdlib.h>
#define maxSize 128
typedef int HElemType;
typedef struct node {                 //大根堆的定义 
    HElemType data[maxSize];             //存放大根堆中元素的数组                        
    int n;                       //大根堆中的当前元素个数 
} Heap;

//大根堆的筛选
void siftDown (Heap &H, int start, int m){
    int i = start;
    int j = 2*i+1;
    HElemType tmp =  H.data[i];
    while(j<=m){
        if(j<m&&H.data[j]<H.data[j+1])
            j++;
        if(tmp >=H.data[j]) break;
        else {
            H.data[i]=H.data[j];
            i = j;
            j = 2*j+1;
        }
    }
    H.data[i] = tmp;
};

//初始化堆
void  HeapInint (Heap &H,int pre[],int m){
    for(int i=0;i<m;i++){
        H.data[i]=pre[i];
    }
    H.n=m;
    for(int i=(H.n-2)/2;i>=0;i--){
        siftDown(H,i,H.n-1);
    }
    for(int i=H.n-1;i>0;i--){
        HElemType tmp = H.data[0];
        H.data[0] = H.data[i];
        H.data[i] = tmp;
        siftDown(H,0,i-1);
    }
} 
 
//输出堆
void printMessage (Heap &H){
    printf("堆的所有数据！\n");
    for(int i =0;i<H.n;i++){
        printf("%d ",H.data[i]);
    }
    return; 
} 

main(){
    Heap H;
    int m;
    printf("输入堆函数的个数：");
    scanf("%d",&m);
    int a[m];
    for(int i=0;i<m;i++){
        printf("输入第%d位堆元素：",i+1); 
        scanf("%d",&a[i]);
    }
    HeapInint (H,a,m);
    printMessage(H);
}