最小最大堆的实现

//最小最大堆的定义,一颗完全二叉树，根节点为最小层，最小层和最大层交替出现，如果x为最小层的节点，那么他就是以x为根节点的二叉树

的最小节点，如果x为最大层的节点，那么他就是以x为根节点的二叉树的最大节点
//支持双端队列的实现（1：能够插入任意一个值 2：能够删除最大值 3：能够删除最小值）
//实现从节点1开始，0舍弃
/*
 * 2008/07/04 By YaoJianming
 * */
#include
#include

#define MAXSIZE 1000
struct element {
        int key;
};
element heap[MAXSIZE];
//判断节点所在是最大还是最小层，最小层返回true
bool level(int i)
{
    double k = log(i)/log(2);
    if((int)k%2 ==0) return true;
    else return false;
}
//在最大层向上追溯
void max_verify(element heap[], int n, element item)
{
        int i = n;
        int parent = n/4;
        while(parent) {
                if(heap[parent].key < item.key) {
                        heap[i] = heap[parent];
                        i = parent;
                        parent = parent/4;
                } else {
                        break;
                }
        }
        heap[i] = item;
}
void min_verify(element heap[], int n, element item)
{
        int i = n;
        int parent = n/4;
        while(parent) {
                if(heap[parent].key > item.key) {
                        heap[i] = heap[parent];
                        i = parent;
                        parent = parent/4;
                } else {
                        break;
                }
        }
        heap[i] = item;
}

void insert(element heap[], int *n, element item)
{
        (*n)++;
        if(*n == MAXSIZE) {
                printf("heap is full\n");
                exit(1);
        }
        if(*n == 1) {
                heap[*n].key = item.key;
                return;
        }
        int parent = *n/2;
        switch(level(parent)) {
        case true:
                if(heap[parent].key > item.key) {
                        heap[*n] = heap[parent];
                        min_verify(heap, parent, item);
                } else {
                        max_verify(heap, *n, item);
                }
                break;
        case false:
                if(heap[parent].key < item.key) {
                        heap[*n] = heap[parent];
                        max_verify(heap, parent, item);
                } else {
                        min_verify(heap, *n, item);
                }
                break;
        }
}
//寻找子节点和后序节点中最小的节点
int min_grand_child(element heap[], int n, int i)
{
        int min = 2*i;
        int k[5] = {2*i+1, 4*i, 4*i+1, 4*i+2, 4*i+3};
        for(int j=0; k[j]<=n&&j<=4; ++j) {
                if(heap[k[j]].key < heap[min].key)
                        min = k[j];
        }
        return min;
}

element del_min(element heap[], int *n)
{
        if(*n < 1) {
                printf("heap is empty\n");
                exit(1);
        }
        if(*n == 1) return heap[(*n)--];//case 1

        element item = heap[(*n)--];
        heap[0].key = heap[1].key;
        int k, i, last = (*n)/2, parent;
        for(i=1; i<=last; ) {
                k = min_grand_child(heap, *n, i);
                if(item.key <= heap[k].key) break;//case 2(a)

                heap[i] = heap[k];

                if(k <= 2*i+1) {//case 2(b)
                        i = k;
                        break;
                }

                parent = k/2;//case 2(c)
                if(item.key > heap[parent].key) {
                        element temp = item;
                        item = heap[parent];
                        heap[parent] = temp;
                }
                i = k;
        }
        heap[i] = item;
        return heap[0];
}

element del_max(element heap[], int *n)
{
 
}

int main()
{
        int n = 0;
        for(int i=1; i<=10; ++i) {
                element item;
                item.key = i;
                insert(heap, &n, item);
        }
        del_min(heap, &n);
        for(int i=1; i<=n; ++i) {
                printf("%d ", heap[i].key);
        }
        printf("\n");

        return 0;
}