steverobinson

Priority Queue [Updated with Delete min, Isempty, IsFull Functions]]

Aug 30th, 2010
144
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 3.02 KB | None | 0 0
  1. //Program to Implement struct binaryheap Queue using Min Heap
  2. #include <stdio.h>
  3. #include <conio.h>
  4.  
  5. //Min heap Declaration
  6. struct binaryheap
  7. {
  8.     int maxsize;
  9.     int size;
  10.     int *elements;
  11. }h;
  12.  
  13. //Function to Check Whether Heap is Empty
  14. int isempty()
  15. {
  16.     if(h.size==0)
  17.         return 1;
  18.     else
  19.         return 0;
  20. }
  21.  
  22. //Function to Check Whether Heap is Full
  23. int isfull()
  24. {
  25.     if(h.size==h.maxsize)
  26.         return 1;
  27.     else
  28.         return 0;
  29. }
  30.  
  31.  
  32. //Function to display elements of the heap
  33. void display()
  34. {
  35.     int i;
  36.     if(isempty())
  37.     {
  38.         printf("\nThe Queue is empty!\n");
  39.     }
  40.     else
  41.     {
  42.     printf("\nThe Elements are: \n");
  43.     for(i=1;i<=h.size;i++)
  44.     {
  45.         printf("\n%d",h.elements[i]);
  46.     }
  47.     }
  48. }
  49.  
  50. //Function to insert elements to the heap
  51. void insert (int x)
  52. {
  53.     int i,temp;
  54.     if(h.size==0)
  55.         {
  56.             h.size++;
  57.             h.elements[1]=x;
  58.         }
  59.     else
  60.     {
  61.         h.size++;
  62.         h.elements[h.size]=x;
  63.         for(i=h.size;h.elements[i]<h.elements[i/2]&&i/2!=0;i=i/2)
  64.         {
  65.             temp=h.elements[i];
  66.             h.elements[i]=h.elements[i/2];
  67.             h.elements[i/2]=temp;
  68.         }
  69.     }
  70. }
  71.  
  72. //Function to delete the minimum element from the heap
  73. void delete_min()
  74. {
  75.     int i=1,x,last;
  76.     if(isempty())
  77.     {
  78.         printf("\nQueue Empty!\n");
  79.     }
  80.     else
  81.     {
  82.     x=h.elements[1];
  83.     last=h.elements[h.size];
  84.     printf("\nThe Deleted Element is: %d\n",h.elements[1]);
  85.     while(i*2<=h.size)
  86.     {
  87.         if(h.elements[i*2]<h.elements[i*2+1])
  88.             {
  89.                 h.elements[i]=h.elements[i*2];
  90.                 i=i*2;
  91.             }
  92.         else
  93.             {
  94.                 h.elements[i]=h.elements[i*2+1];
  95.                 i=i*2+1;
  96.             }
  97.     }
  98.     h.elements[i]=last;
  99.     h.size--;
  100.     }
  101. }
  102.  
  103. int  main()
  104. {
  105.     int temp,ch,i;
  106.     h.size=0;
  107.     printf("\nEnter Maximum Number of Elements in the Queue: ");
  108.     scanf("%d",&h.maxsize);
  109.     h.elements=(int *)malloc((h.maxsize+1)*sizeof(int));
  110.     menu:
  111.     printf("\nMenu:\n1. Insert Elements\n2. Display Heap\n3. Delete Minimum Element\n4. Exit\nEnter Choice.....");
  112.     scanf("%d",&ch);
  113.  
  114.     switch(ch)
  115.     {
  116.         case 1:
  117.             do{
  118.                 if(!isfull())
  119.                 {
  120.                     printf("\nEnter the element: ");
  121.                     scanf("%d",&temp);
  122.                     insert(temp);
  123.                 }
  124.                 else
  125.                 {
  126.                     printf("\nQueue Full!\n");
  127.                     goto menu;
  128.                 }
  129.                 printf("\nInsert More ? Yes (1) No (0)");
  130.                 scanf("%d",&ch);
  131.             }while(ch);
  132.             break;
  133.  
  134.       case 2:
  135.         display();
  136.         break;
  137.  
  138.       case 3:
  139.         delete_min();
  140.         break;
  141.  
  142.       case 4:
  143.         printf("\nThank You!");
  144.         getch();
  145.         return 0;
  146.  
  147.       default:
  148.         printf("\nInvalid choice!\n");
  149.         goto menu;
  150.  
  151.     }
  152.  
  153.     goto menu;
  154.  
  155. }
Add Comment
Please, Sign In to add comment