双端堆的实现

//双端堆的特点：顶点为空，左边为最小堆，右边为最大堆

//插入的时候，最小堆节点i对应的最大堆节点为j，且j=(i+2^(logn/log2-1))/2,heap[i]必然小于heap[j]

//最大堆节点i对应的最小堆节点为j，且j=i-2^(logn/log2-1),heap[i]必然大于heap[j]

 

/*
 * 2008/07/04 By YaoJianming
 * */
#include
#include
#include

#define MAXSIZE 1000
struct element {
        int key;
};
element heap[MAXSIZE];

void min_verify(element heap[], int i, element item)
{
        int parent = i/2;
        while(parent > 1) {
                if(item.key < heap[parent].key) {
                        heap[i] = heap[parent];
                        i = parent;
                        parent /=2;
                } else {
                        break;
                }
        }
        heap[i] = item;
}

void max_verify(element heap[], int i, element item)
{
        int parent = i/2;
        while(parent > 1) {
                if(item.key > heap[parent].key) {
                        heap[i] = heap[parent];
                        i = parent;
                        parent /= 2;
                } else {
                        break;
                }
        }
        heap[i] = item;
}

bool max_heap(int n)
{
        double a = log(n)/log(2);
        double f = n + pow(2, (int)a-1);
        double b = log(f)/log(2);
        if((int)a == (int)b) return false;
        else return true;
}

int min_partner(int n)
{
        double k = log(n)/log(2);
        double a = pow(2, (int)k-1);
        return n - (int)a;
}

int max_partner(int n)
{
        double k = log(n)/log(2);
        double a = pow(2, (int)k-1);
        return (n + (int)a)/2;
}

void insert(element heap[], int &n, element item)
{
        ++n;
        if(n == MAXSIZE) {
                printf("heap is full\n");
                exit(1);
        }

        if(n == 2) {
                heap[n] = item;
                return;
        }

        int i;
        switch(max_heap(n)) {
        case true:
                i = min_partner(n);
                if(item.key < heap[i].key) {
                        heap[n] = heap[i];
                        min_verify(heap, i, item);
                } else {
                        max_verify(heap, n, item);
                }
                break;
        case false:
                i = max_partner(n);
                if(item.key > heap[i].key) {
                        heap[n] = heap[i];
                        max_verify(heap, i, item);
                } else {
                        min_verify(heap, n, item);
                }
        }
}

element del_min(element heap[], int &n)
{
        if(n == 2) return heap[n--];

        heap[1] = heap[2];
        heap[2] = heap[n--];
        int k = 2;
        while(2*k < n) {
                element min = heap[2*k].key < heap[2*k+1].key ? heap[2*k] : heap[2*k+1];
                int pos = heap[2*k].key < heap[2*k+1].key ? 2*k : 2*k+1;
                if(heap[k].key > heap[pos].key) {
                        element temp = heap[k];
                        heap[k] = heap[pos];
                        heap[pos] = temp;
                        k = pos;
                } else {
                        break;
                }
        }
        double i = log(k)/log(2);
        double j = pow(2, (int)i-1);
        int m = k + (int)j;
        if(m > n) m = m/2;
        if(heap[k].key > heap[m].key) {
                element temp = heap[k];
                heap[k] = heap[m];
                heap[m] = temp;
        }
        return heap[1];
}

element del_max(element heap[], int &n)
{

}

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