minheap.cpp

#include<stdio.h>

#define MAX_HEAP_SIZE 100000

#define MAXREAL 999999.0

class HeapItem
{
public:
    int data;
    float key;
};


class MinHeap
{
public:
    HeapItem * A;
    int heapLength;
    int * map;

    MinHeap()
    {
        A = new HeapItem[MAX_HEAP_SIZE];
        map = new int[MAX_HEAP_SIZE];
        heapLength=0;
    }

    ~MinHeap()
    {
        if(map) delete [] map;
        if(A) delete [] A;
        map = 0;
        A = 0;
    }


    void initialize(int v[], int n)
    {
        heapLength = n;
        for(int i=0; i<n; i++)   {
            A[i+1].data = v[i];
            A[i+1].key = MAXREAL;
            map[v[i]] = i+1;    }
    }

    void insertItem(int data, float key)
    {
        HeapItem t;
        t.data=data;
        t.key=key;
        heapLength++;
        A[heapLength]=t;

        map[t.data]=heapLength;

        buHeapify(heapLength);

    }

    HeapItem removeMin()
    {
        HeapItem h=A[1];
        A[1]=A[heapLength];
        heapLength--;
        heapify(1);

        return h;

    }



    void updateKey(int data, float key)
    {

        int x=map[data];
        if(x==0){
            printf("No such element\n");
            return;
        }
        if(key>A[x].key)
        {
            A[x].key=key;
            heapify(x);
        }
        else
        {
            A[x].key=key;
            buHeapify(x);
        }

    }


    float getKey(int data)
    {

        int i = map[data];
        return A[i].key;
    }


    void heapify(int i)
    {
        int l,r,smallest;
		while(1)
		{
			l=2*i;      //left child index
			r=2*i+1;    //right child index
			smallest=i;

			if(l>heapLength && r>heapLength)
				break; //nothing to do, we are at bottom
			else if(r>heapLength)
				smallest = l;
			else if(l>heapLength)
				smallest = r;
			else if( A[l].key < A[r].key )
				smallest = l;
			else
				smallest = r;

			if(A[i].key <= A[smallest].key)
				break;
            else
			{
				HeapItem t;
				t=A[i];
				A[i]=A[smallest];
				map[A[i].data]=i;
				A[smallest]=t;
				map[A[smallest].data]=smallest;
				i=smallest;
			}

		}
    }


    void buHeapify(int i)
    {
        if(i==1) return;
        if(A[i/2].key<A[i].key&&i>0) return;


        else
        {

            HeapItem t;
            t=A[i];
            A[i]=A[i/2];
            map[A[i].data]=i;
            A[i/2]=t;
            map[A[i/2].data]=i/2;
            i=i/2;
            buHeapify(i);
        }

    }

    void printHeap()
    {
        printf("Heap length: %d\n", heapLength);
        for(int i=1; i<=heapLength; i++)
        {
            printf("(%d,%.2f) ", A[i].data, A[i].key);
        }
        printf("\n");
    }

    bool Empty()
    {
        if(heapLength==0)return true;
        else return false;
    }
};


int main()
{
    int choice;
    int data;
    float key;
    MinHeap heap;
    bool exit = false;
    while(!exit)
    {
        printf("1. Insert 2. RemoveMin 3.Update 4. Print 5.getkey 6. Exit.\n");
        scanf("%d",&choice);
        switch(choice)
        {
        case 1:
            scanf("%d%f",&data,&key);
            //printf("%d%f\n",data,key);
            heap.insertItem(data, key);
            heap.printHeap();
            break;
        case 2:
            if(heap.heapLength==0)

            {
                printf("UNDERFLOW\n");
                break;
            }

            HeapItem item;
            item = heap.removeMin();
            printf("Removed: (%d,%.2f)\n", item.data, item.key);
            heap.printHeap();
            break;
        case 3:
            scanf("%d%f",&data,&key);
            heap.updateKey(data,key);
            heap.printHeap();
            break;
        case 4:
            heap.printHeap();
            break;
        case 5:
            int data;
            scanf("%d",&data);
            printf("%f\n",heap.getKey(data));
            break;
        case 6:
            exit = true;
            break;

        }
    }
    return 0;
}