小大根交替堆实现双端优先队列

/***************************************************************************
*            heap.h
*
*  Mon Sep  4 10:19:52 2006
*  Copyright  2006  wangyao
*  Email:[e-mail]
****************************************************************************/

#include
#include
#include

#define MAX_SIZE 100 /*Max size of heap*/
#define COMMENT_SIZE 50
#define FALSE 0
#define TRUE 1
#define SWAP(x,y,t) ((t)=(x),(x)=(y),(y)=(t))
typedef struct{
    int key;
    char comment[COMMENT_SIZE];
    /*Other fields*/
} element;

element heap[MAX_SIZE]; /* Global variable reference*/

int level(int node)
{
    int level = 0;
    double level_double;

    level_double = log10((double)node)/log10((double)2); /* base-2 logarithmic function*/
    level = (int)floor(level_double); /*largest integral value not greater than argument*/

    if(level % 2 == 0)
        return 0; /*Min Level*/
    else
        return 1; /*Max Level*/
}

/*Find the minimum of the heap*/
int findmin(element heap[])
{
    return heap[1].key;
}

/*Find the maximum of the heap*/
int findmax(element heap[])
{
    if(heap[2].key < heap[3].key)
        return heap[3].key;
    else
        return heap[2].key;
}


void verify_max(element heap[],int i,element item)
{
    /*follow the nodes from the max node i to the root
    and insert item into its proper place*/

    int grandparent = i/4;

    while(grandparent)
    {
        if(item.key > heap[grandparent].key){
            heap[i] = heap[grandparent];
            i = grandparent;
            grandparent /= 4;
        }
        else
            break;
    }

    heap[i] = item;
}

void verify_min(element heap[],int i,element item)
{
    /*floow the nodes from the min node i into the root and
    insert item into its proper place*/
    int grandparent = i/4;
    while(grandparent)
    {
        if(item.key < heap[grandparent].key)
        {
            heap[i] = heap[grandparent];
            i = grandparent;
            grandparent /= 4;
        }
        else
            break;
    }

    heap[i] = item;
}


int min_child_grandchild(int node,int number)
/*Get the minimum of the node's children and grandchildren*/
{
    int minnode = 2*node;

    /* Judge if the node exist or not.*/
    if(heap[2*node].key)
        minnode = 2*node;
    if((heap[2*node+1].key) && (heap[2*node+1].key < heap[2*node].key))
        minnode = 2*node+1;
    if((heap[4*node].key) && (heap[4*node].key < heap[minnode].key))
        minnode = 4*node;
    if((heap[4*node+1].key) && (heap[4*node+1].key < heap[minnode].key))
        minnode = 4*node +1;
    if((heap[4*node+2].key) && (heap[4*node+2].key < heap[minnode].key))
        minnode = 4*node +2;
    if((heap[4*node+3].key) && (heap[4*node+3].key < heap[minnode].key))
        minnode = 4*node +3;

    return minnode;
}

int max_child_grandchild(int node,int number)
/*Get the maximum of the node's children and grandchildren*/
{
    int maxnode = 2*node;
   
    /* Judge if the node exist or not.*/
    if(heap[2*node].key)
        maxnode = 2*node;
    if((heap[2*node+1].key) && (heap[2*node+1].key > heap[2*node].key))
        maxnode = 2*node+1;
    if((heap[4*node].key) && (heap[4*node].key > heap[maxnode].key))
        maxnode = 4*node;
    if((heap[4*node+1].key) && (heap[4*node+1].key > heap[maxnode].key))
        maxnode = 4*node +1;
    if((heap[4*node+2].key) && (heap[4*node+2].key > heap[maxnode].key))
        maxnode = 4*node +2;
    if((heap[4*node+3].key) && (heap[4*node+3].key > heap[maxnode].key))
        maxnode = 4*node +3;

    return maxnode;
}

void min_max_insert(element heap[],int n,element item)
{
    /*Insert item into the min_max heap*/
    int parent;
    n++;

    if(n == MAX_SIZE ){
        fprintf(stderr,"The heap is full!\n");
        exit(1);
    }

    parent = n/2;
    if(!parent)
        heap[1] = item;/*Heap is empty,insert item into first postion*/
    else switch(level(parent)){
        case FALSE:/*min level*/
            if(item.key < heap[parent].key){
                heap[n] = heap[parent]; /*place the parent into the *n node*/
                verify_min(heap,parent,item); /*adjust the min heap from parent to root*/
            }
            else
                verify_max(heap,n,item); /*adjust the max heap from *n node to root*/
            break;
        case TRUE:/*max level*/
            if(item.key > heap[parent].key){
                heap[n] = heap[parent]; /*place the parent to the *n node*/
                verify_max(heap,parent,item); /*adjust the max heap from parent node to root*/
            }
            else
                verify_min(heap,n,item); /*adjust the min heap from *n node to root*/
    }
}

element del_min(element heap[],int n)
{
    /*Delete the minimum element from the min-max heap*/
    int i,last,k,parent;
    element temp,item;

    if(!n){
        fprintf(stderr,"The heap is empty!\n");
        heap[0].key = INT_MAX;
        return heap[0];
    }

    heap[0] = heap[1]; /*heap[1] is root,and is the minimum.
                       Place heap[1] into heap[0],then return it*/
    item = heap[n--]; /*item is the last element of the heap*/
    last = n/2;
    /*Find the proper place i to insert the item*/
    for(i = 1;i <= last;){
        k = min_child_grandchild(i,n); /*k is the minimum of the node i's childs and grandchilds*/
        //printf("The min of node %d is %d.\n",i,k);
        /*Case 2(a)*/
        if(item.key <= heap[k].key)
            break;

        /* Case 2(b) or 2(c),item.key > heap[k].key*/       
        heap[i] = heap[k]; /*k node is the minimum of the (child) heap,place it into the node i*/

        /* Case 2(b)*/
        if(k <= 2*i+1){
            i = k; /*k is Max Node,its children not greater than it,
                   Place the i node into the k node,satisfy the max heap */
            break;           
        }

        /*Case 2(c)*/
        parent = k/2; /*Node k is Node i's grandchild,get its parent*/
        if(item.key > heap[parent].key)
            SWAP(heap[parent],item,temp);

        i = k; /*Place the i into k*/
    } /*for circle,until the heap staisfy min-max heap*/

    heap[i] = item; /*i is the proper place get by above for circle*/
    return heap[0];
}

element del_max(element heap[],int n)
{
    /*Delete the maximum element from the min-max heap*/
    int i,begin=2,last,k,parent;
    element temp,item;

    if(!n){
        fprintf(stderr,"The heap is empty!\n");
        heap[0].key = INT_MAX;
        return heap[0];
    }

    heap[0] = heap[2]; /*heap[1] is root,and is the minimum.
                       Place heap[1] into heap[0],then return it*/
    if(heap[2].key < heap[3].key)
    {
        heap[0] = heap[3];
        begin = 3;
    }

    item = heap[n--]; /*item is the last element of the heap*/
    last = n/2;
    /*Find the proper place i to insert the item*/
    for(i = begin;i <= last;){
        k = max_child_grandchild(i,n); /*k is the minimum of the node i's childs and grandchilds*/

        /*Case 2(a)*/
        if(item.key >= heap[k].key)
            break;

        /* Case 2(b) or 2(c),item.key < heap[k].key*/       
        heap[i] = heap[k]; /*k node is the maximum of the (child) heap,place it into the node i*/

        /* Case 2(b)*/
        if(k <= 2*i+1){
            i = k; /*k is Min Node,its children greater than it,
                   Place the i node into the k node,satisfy the min heap */
            break;           
        }

        /*Case 2(c)*/
        parent = k/2; /*Node k is Node i's grandchild,get its parent*/
        if(item.key < heap[parent].key)
            SWAP(heap[parent],item,temp);

        i = k; /*Place the i into k*/
    } /*for circle,until the heap satisfy min-max heap*/

    heap[i] = item; /*i is the proper place get by above for circle*/
    return heap[0];
}

void adjust(element heap[],int root,int n)
/*Adjust the binary tree to establish the min max heap.*/
{
    int child,tempnode;
    element swapelement;

    child = 2*root; /*left child*/
   
    if(child <= n)
    {
    /*root node is in min level*/
        if((level(root) == 0) && (child <= n))
        {       
            /*get the min key value's node of the node root's children and grandchildren*/
            tempnode = min_child_grandchild(root,n);

            /*if the root node's key greater than the max key,swap them*/
            if(heap[root].key > heap[tempnode].key)
                SWAP(heap[root],heap[tempnode],swapelement);
        }
        /*root node is in max level*/
        else if(level(root) && (child <= n))   
        {
            /*get the max key value's node of the node root's children and grandchildren*/
            tempnode = max_child_grandchild(root,n);

            /*if the root node's key letter than the max key,swap them*/
            if(heap[root].key < heap[tempnode].key)
                SWAP(heap[root],heap[tempnode],swapelement);
        }

        /*call the adjust by recursion,
        to make all the non-leaf node satisfy the min max heap*/
        adjust(heap,child,n);
        /*if the child's brother exist,also adjust it.*/
        if(child < n)
            adjust(heap,child+1,n);       
    }
    else
        return;
}

void heapinit(element heap[],int number)
/* Perform a min max heap sort on the array*/
{
    int i = 0;

    /*Adjust all nodes in log2(n)-2 levels*/
    for(i = number/4;i>0;i--)
        adjust(heap,i,number);
}