heap

/*
 *实现最小堆
 */
#include <stdio.h>

#define MAXSIZE 1024
int myHeap[MAXSIZE];
int sz = 0;     //sz记录当前堆得大小

//将新来的节点插入到堆的最后面
void push(int x){
    if(sz > MAXSIZE)
      printf("The heap cannot hold any element\n");
    int i = sz++;    //i记录当前要插入的节点的index

    while(i > 0){
        int p = (i - 1)/2;
        //向上找到小于x的节点
        if(myHeap[p] <= x) break;
        myHeap[i] = myHeap[p];
        i = p;
    }
    myHeap[i] = x;
}

int top(){
    return myHeap[0];
}

int pop(){
    if(sz < 1)
      printf("The heap is empty\n");
    int res = myHeap[0];

    int x = myHeap[--sz];

    int i = 0;

    while(2*i + 1 < sz){
        int a = 2*i + 1, b = 2*i +2;

        if(myHeap[a] > myHeap[b])    a = b;

        if(myHeap[a] >= x ) break;

        myHeap[i] = myHeap[a];
        i = a;
    }
    myHeap[i] = x;

    return res;
}


int main(){
    push(9);
    push(8);
    push(7);
    push(6);
    push(5);
    push(4);

    printf("%d\n", pop());

    printf("%d\n", pop());

}