C++ Program to Implement D-ary-Heap

«
»
This C++ Program demonstrates the implementation of D-ary Heap.

Here is source code of the C++ Program to demonstrate the implementation of D-ary Heap. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  *  C++ Program to Implement D-ary-Heap
  3.  */
  4. #include <iostream>
  5. #include <cstring>
  6. #include <cstdlib>
  7. using namespace std;
  8. /*
  9.  *   D-ary Heap Class
  10.  */
  11. class DaryHeap
  12. {
  13.     private:
  14.         int d;
  15.         int currentSize;
  16.         int size;
  17.         int *array;
  18.     public:
  19.         /*
  20.          * Constructor 
  21.          */
  22.         DaryHeap(int capacity, int numKids)
  23.         {
  24.             currentSize = 0;
  25.             d = numKids;
  26.             size = capacity + 1;
  27.             array = new int[capacity + 1];
  28.             for (int i = 0 ; i < capacity + 1; i++)
  29.                 array[i] = -1;
  30.         }
  31.  
  32.         /*
  33.          * Constructor , filling up heap with a given array 
  34.          */
  35.         DaryHeap(int* array, int numKids)
  36.         {
  37.             int i = 0;
  38.             while (array[i] != -1)
  39.                 i++;
  40.             currentSize = i;
  41.             this->array = array;
  42.             this->d = numKids;
  43.             buildHeap();
  44.         }
  45.  
  46.         /*
  47.          * Function to check if heap is empty 
  48.          */
  49.         bool isEmpty()
  50.         {
  51.             return currentSize == 0;
  52.         }
  53.  
  54.         /*
  55.          * Check if heap is full 
  56.          */
  57.         bool isFull()
  58.         {
  59.             return currentSize == size;
  60.         }
  61.  
  62.         /*
  63.          * Clear heap 
  64.          */
  65.         void makeEmpty( )
  66.         {
  67.             currentSize = 0;
  68.         }
  69.  
  70.         /*
  71.          * Function to  get index parent of i 
  72.          */
  73.         int parent(int i)
  74.         {
  75.             return (i - 1) / d;
  76.         }
  77.  
  78.         /*
  79.          * Function to get index of k th child of i 
  80.          */
  81.         int kthChild(int i, int k)
  82.         {
  83.             return d * i + k;
  84.         }
  85.  
  86.         /*
  87.          * Function to inset element 
  88.          */
  89.         void insert(int x)
  90.         {
  91.             if (isFull())
  92.             {
  93.                 cout<<"Array Out of Bounds"<<endl;
  94.                 return;
  95.             }
  96.             int hole = currentSize;
  97.             currentSize++;
  98.             array[hole] = x;
  99.             percolateUp(hole);
  100.         }
  101.  
  102.         /*
  103.          * Function to find least element 
  104.          */
  105.         int findMin()
  106.         {
  107.             if (isEmpty())
  108.             {
  109.                 cout<<"Array Underflow"<<endl;
  110.                 return 0;
  111.             }
  112.             return array[0];
  113.         }
  114.         /*
  115.          * Function to delete element at an index 
  116.          */
  117.         int Delete(int hole)
  118.         {
  119.             if (isEmpty())
  120.             {
  121.                 cout<<"Array Underflow"<<endl;
  122.                 return 0;
  123.             }
  124.             int keyItem = array[hole];
  125.             array[hole] = array[currentSize - 1];
  126.             currentSize--;
  127.             percolateDown( hole );
  128.             return keyItem;
  129.         }
  130.  
  131.         /*
  132.          * Function to build heap 
  133.          */
  134.         void buildHeap()
  135.         {
  136.             for (int i = currentSize - 1 ; i >= 0; i--)
  137.                 percolateDown(i);
  138.         }
  139.  
  140.         /*
  141.          * Function percolateDown 
  142.          */
  143.         void percolateDown(int hole)
  144.         {
  145.             int child;
  146.             int tmp = array[hole];
  147.             for ( ; kthChild(hole, 1) < currentSize; hole = child)
  148.             {
  149.                 child = smallestChild( hole );
  150.                 if (array[child] < tmp)
  151.                     array[hole] = array[child];
  152.                 else
  153.                     break;
  154.             }
  155.             array[hole] = tmp;
  156.         }
  157.  
  158.         /*
  159.          * Function to get smallest child from all valid indices 
  160.          */
  161.         int smallestChild(int hole)
  162.         {
  163.             int bestChildYet = kthChild(hole, 1);
  164.             int k = 2;
  165.             int candidateChild = kthChild(hole, k);
  166.             while ((k <= d) && (candidateChild < currentSize))
  167.             {
  168.                 if (array[candidateChild] < array[bestChildYet])
  169.                     bestChildYet = candidateChild;
  170.                 k++;
  171.                 candidateChild = kthChild(hole, k);
  172.             }
  173.             return bestChildYet;
  174.         }
  175.  
  176.         /*
  177.          * Function percolateUp  
  178.          */
  179.         void percolateUp(int hole)
  180.         {
  181.             int tmp = array[hole];
  182.             for (; hole > 0 && tmp < array[parent(hole)]; hole = parent(hole))
  183.                 array[hole] = array[ parent(hole) ];
  184.             array[hole] = tmp;
  185.         }
  186.  
  187.         /*
  188.          * Function to print heap 
  189.          */
  190.         void printHeap()
  191.         {
  192.             cout<<"\nHeap = ";
  193.             for (int i = 0; i < currentSize; i++)
  194.                 cout<<array[i]<<"   ";
  195.             cout<<endl;
  196.         }
  197. };
  198. /*
  199.  * Main
  200.  */
  201. int main()
  202. {
  203.     cout<<"Dary Heap Test\n\n";
  204.     cout<<"Enter size and D of Dary Heap: ";
  205.     int size, num, choice, val;
  206.     cin>>size>>num;
  207.     DaryHeap th(size, num);
  208.     char ch;
  209.     do
  210.     {
  211.         cout<<"\nDary Heap Operations\n";
  212.         cout<<"1. Insert "<<endl;
  213.         cout<<"2. Delete"<<endl;
  214.         cout<<"3. Check full"<<endl;
  215.         cout<<"4. Check empty"<<endl;
  216.         cout<<"5. Clear"<<endl;
  217.         bool chk;
  218.         cout<<"Enter your Choice: ";
  219.         cin>>choice;
  220.         switch (choice)
  221.         {
  222.         case 1:
  223.             cout<<"Enter integer element to insert: ";
  224.             cin>>val;
  225.             th.insert(val);
  226.             break;
  227.         case 2:
  228.             cout<<"Enter delete position: ";
  229.             cin>>val;
  230.             th.Delete(val - 1);
  231.             break;
  232.         case 3:
  233.             if (th.isFull())
  234.                 cout<<"The Heap is Full"<<endl;
  235.             else
  236.                 cout<<"The Heap is not Full"<<endl;
  237.             break;
  238.         case 4 :
  239.             if (th.isEmpty())
  240.                 cout<<"The Heap is Empty"<<endl;
  241.             else
  242.                 cout<<"The Heap is not Empty"<<endl;
  243.             break;
  244.         case 5 :
  245.             th.makeEmpty();
  246.             cout<<"Heap Cleared\n";
  247.             break;
  248.         default :
  249.             cout<<"Wrong Entry \n ";
  250.             break;
  251.         }
  252.         th.printHeap();
  253.         cout<<"\nDo you want to continue (Type y or n) \n";
  254.         cin>>ch;
  255.     }
  256.     while (ch == 'Y'|| ch == 'y');
  257.     return 0;
  258. }

advertisement
$ g++ dary_heap.cpp
$ a.out
 
Dary Heap Test
 
Enter size and D of Dary Heap: 6 3
 
Dary Heap Operations
1. Insert
2. Delete
3. Check full
4. Check empty
5. Clear
Enter your Choice: 1
Enter integer element to insert: 24
 
Heap = 24
 
Do you want to continue (Type y or n)
y
 
Dary Heap Operations
1. Insert
2. Delete
3. Check full
4. Check empty
5. Clear
Enter your Choice: 1
Enter integer element to insert: 6
 
Heap = 6   24
 
Do you want to continue (Type y or n)
y
 
Dary Heap Operations
1. Insert
2. Delete
3. Check full
4. Check empty
5. Clear
Enter your Choice: 1
Enter integer element to insert: 23
 
Heap = 6   24   23
 
Do you want to continue (Type y or n)
y
 
Dary Heap Operations
1. Insert
2. Delete
3. Check full
4. Check empty
5. Clear
Enter your Choice: 1
Enter integer element to insert: 12
 
Heap = 6   24   23   12
 
Do you want to continue (Type y or n)
y
 
Dary Heap Operations
1. Insert
2. Delete
3. Check full
4. Check empty
5. Clear
Enter your Choice: 1
Enter integer element to insert: 75
 
Heap = 6   24   23   12   75
 
Do you want to continue (Type y or n)
y
 
Dary Heap Operations
1. Insert
2. Delete
3. Check full
4. Check empty
5. Clear
Enter your Choice: 1
Enter integer element to insert: 78
 
Heap = 6   24   23   12   75   78
 
Do you want to continue (Type y or n)
y
 
Dary Heap Operations
1. Insert
2. Delete
3. Check full
4. Check empty
5. Clear
Enter your Choice: 1
Enter integer element to insert: 29
 
Heap = 6   24   23   12   75   78   29
 
Do you want to continue (Type y or n)
y
 
Dary Heap Operations
1. Insert
2. Delete
3. Check full
4. Check empty
5. Clear
Enter your Choice: 2
Enter delete position: 5
 
Heap = 6   24   23   12   29   78
 
Do you want to continue (Type y or n)
y
 
Dary Heap Operations
1. Insert
2. Delete
3. Check full
4. Check empty
5. Clear
Enter your Choice: 2
Enter delete position: 6
 
Heap = 6   24   23   12   29
 
Do you want to continue (Type y or n)
y
 
Dary Heap Operations
1. Insert
2. Delete
3. Check full
4. Check empty
5. Clear
Enter your Choice: 2
Enter delete position: 3
 
Heap = 6   24   29   12
 
Do you want to continue (Type y or n)
y
 
Dary Heap Operations
1. Insert
2. Delete
3. Check full
4. Check empty
5. Clear
Enter your Choice: 5
Heap Cleared
 
Heap =
 
Do you want to continue (Type y or n)
n
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn