Saturday, January 21, 2012

Heaps and priority queues: Complete C program with sorting and all other functions ( Cormen C implementation)


"
#include<stdio.h>

#define EXCHANGE(x,y,z) {z=x;x=y;y=z;}

void printheap(int *);
void max_heapify(int *,int);
void build_max_heap(int *);
void heapsort(int *);
int heap_extract_max(int *);
int heap_maximum(int *);
void heap_increase_key(int *,int ,int);
void max_heap_insert(int *,int);

int n=10;
main()
{
    int heap[]={0,16,14,10,8,7,9,3,2,4,1,0,0,0};
    // int n=9 is a global variable
    printheap(heap);
    heap_increase_key(heap,9,15);
    printheap(heap);
}

void printheap(int *heap)
{
    int i;
    for(i=1;i<=n;i++)
    printf("%d,",heap[i]);
    printf("\n");
}

void max_heapify(int *heap,int i)
{
    int left,right,largest;
    left=2*i;
    right=2*i + 1;

    if(heap[left]>heap[i] && left<=n)
    largest=left;
    else
    largest=i;

    if(heap[right]>heap[largest] && right<=n)
    largest=right;

    if(largest != i)
    {
        int temp;
        temp=heap[i];
        heap[i]=heap[largest];
        heap[largest]=temp;

        max_heapify(heap, largest);
    }
}

void build_max_heap(int *heap)
{
    int i;
    for(i=n/2;i>0;i--)
    {
        max_heapify(heap,i);
    }
}

void heapsort(int *heap)
{
    int i,temp,k=n;
    build_max_heap(heap);
    for(i=n;i>0;i--)
    {
        temp=heap[1];
        heap[1]=heap[i];
        heap[i]=temp;
        n--;
        max_heapify(heap,1);
    }
    n=k;
}

int heap_extract_max(int *heap)
{
    int temp;
    temp=heap[1];
    heap[1]=heap[n];
    n--;
    max_heapify(heap,1);
    return temp;
}

void max_heap_insert(int *heap,int key)
{
    n++;
    heap[n]=-100;
    heap_increase_key(heap,n,key);
}
int heap_maximum(int* heap)
{
    return heap[1];
}

void heap_increase_key(int *heap,int i, int key)
{
    int temp;
    heap[i]=key;
    while(heap[i/2]<key && i>1)
    {
        EXCHANGE(heap[i],heap[i/2],temp);
        i/=2;
    }
}
"

2 comments: