C++ Program to Implement Ternary Heap

«
»
This C++ Program demonstrates the implementation of Ternary Heap.

Here is source code of the C++ Program to demonstrate the implementation of Ternary 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 Ternary Heap
  3.  */
  4. #include <iostream>
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <algorithm>
  8. #include <cmath>
  9. #include <vector>
  10. #include <cstdlib>
  11. int const N = 16;
  12. using namespace std;
  13. /*
  14.  * Ternary Heap Class Declaration
  15.  */
  16. class Ternary_Heap
  17. {
  18.     private:
  19.         int heap_capacity;
  20.         int initial_capacity;
  21.         int *array;
  22.         int heap_size;
  23.         void double_capacity()
  24.         {
  25.             int *tmp_array = new int[2 * capacity()];
  26.             for (int i = 0; i < size(); ++i)
  27.             {
  28.                 tmp_array[i] = array[i];
  29.             }
  30.             delete [] array;
  31.             array = tmp_array;
  32.             heap_capacity *= 2;
  33.         }
  34.         void halve_capacity()
  35.         {
  36.             int *tmp_array = new int[capacity() / 2];
  37.             for (int i = 0; i < size(); ++i)
  38.             {
  39.                 tmp_array[i] = array[i];
  40.             }
  41.             delete [] array;
  42.             array = tmp_array;
  43.             heap_capacity /= 2;
  44.         }
  45.     public:
  46.         Ternary_Heap(int);
  47.         ~Ternary_Heap();
  48.         Ternary_Heap(Ternary_Heap &);
  49.         Ternary_Heap &operator=(Ternary_Heap &heap);
  50.         friend ostream &operator <<(ostream &, Ternary_Heap &);
  51.         /*
  52.          * Check if Heap is Empty
  53.          */
  54.         bool empty()
  55.         {
  56.             return heap_size == 0;
  57.         }
  58.         /*
  59.          * Return Size of the Heap
  60.          */
  61.         int size()
  62.         {
  63.             return heap_size;
  64.         }
  65.         /*
  66.          * Return Capacity of the Heap
  67.          */
  68.         int capacity()
  69.         {
  70.             return heap_capacity;
  71.         }
  72.         /*
  73.          * Count elements in the Heap
  74.          */
  75.         int count(int &obj)
  76.         {
  77.             int c = 0;
  78.             for (int i = 0; i < size(); i++)
  79.             {
  80.              if (array[i] == obj)
  81.                 ++c;
  82.             }
  83.             return c;
  84.         }
  85.         /*
  86.          * Returns Top element of the Heap
  87.          */
  88.         int top()
  89.         {
  90.             if (empty())
  91.                 return NULL;
  92.             return array[0];
  93.         }
  94.         /*
  95.          * Push the element into the Heap
  96.          */
  97.         void push(int &obj)
  98.         {
  99.             if (size() == capacity())
  100.                 double_capacity();
  101.             int i = heap_size;
  102.             ++heap_size;
  103.             while (i != 0 && array[(i - 1) / 3] > obj)
  104.             {
  105.                 array[i] = array[(i - 1) / 3];
  106.                 i = (i - 1) / 3;
  107.             }
  108.             array[i] = obj;
  109.         }
  110.         /*
  111.          * Remove element from the Heap
  112.          */
  113.         void pop()
  114.         {
  115.             if (empty())
  116.                 return;
  117.             --heap_size;
  118.             int last = array[size()];
  119.             int posn = 0;
  120.             int posn30 = 0;
  121.             int posn33 = 3;
  122.             while (posn33 < size())
  123.             {
  124.                 int posn31  = posn30 + 1;
  125.                 int posn32 = posn30 + 2;
  126.                 int min = last;
  127.                 int loc = posn;
  128.                 if (array[posn33] < min)
  129.                 {
  130.                     min = array[posn33];
  131.                     loc = posn33;
  132.                 }
  133.                 if (array[posn32] < min)
  134.                 {
  135.                     min = array[posn32];
  136.                     loc = posn32;
  137.                 }
  138.                 if (array[posn31] < min)
  139.                 {
  140.                     min = array[posn31];
  141.                     loc = posn31;
  142.                 }
  143.                 array[posn] = min;
  144.                 if (posn == loc)
  145.                 {
  146.                     if (4 * size() == capacity())
  147.                     {
  148.                         if (capacity() > initial_capacity)
  149.                         {
  150.                             halve_capacity();
  151.                         }
  152.                     }
  153.                     return;
  154.                 }
  155.                 posn = loc;
  156.                 posn30 = 3 * loc;
  157.                 posn33 = posn30 + 3;
  158.             }
  159.             int min = last;
  160.             int loc = posn;
  161.             int posn31 = posn30 + 1;
  162.             int posn32 = posn30 + 2;
  163.             switch (posn33 - size())
  164.             {
  165.             case 0:
  166.                 if (array[posn32] < min)
  167.                 {
  168.                     min = array[posn32];
  169.                     loc = posn32;
  170.                 }
  171.             case 1:
  172.                 if (array[posn31] < min)
  173.                 {
  174.                     min = array[posn31];
  175.                     loc = posn31;
  176.                 }
  177.             }
  178.             array[posn] = min;
  179.             if (posn != loc)
  180.             {
  181.                 array[loc] = last;
  182.             }
  183.         }
  184.         /*
  185.          * Clear Heap
  186.          */
  187.         void clear()
  188.         {
  189.             heap_size = 0;
  190.             if (heap_capacity != initial_capacity)
  191.             {
  192.                 heap_capacity = initial_capacity;
  193.                 delete [] array;
  194.                 array = new int[heap_capacity];
  195.             }
  196.         }
  197. };
  198. Ternary_Heap::Ternary_Heap(int n)
  199. {
  200.     heap_capacity = max(1, n);
  201.     initial_capacity = heap_capacity;
  202.     array = new int [heap_capacity];
  203.     heap_size = 0;
  204. }
  205.  
  206. Ternary_Heap::~Ternary_Heap()
  207. {
  208.     delete [] array;
  209. }
  210.  
  211. Ternary_Heap::Ternary_Heap(Ternary_Heap &heap)
  212. {
  213.     heap_capacity = heap.heap_capacity;
  214.     initial_capacity = heap.initial_capacity;
  215.     array = new int [heap_capacity];
  216.     heap_size = heap.heap_size;
  217.     for (int i = 0; i < heap_size; i++)
  218.     {
  219.         array[i] = heap.array[i];
  220.     }
  221. }
  222.  
  223. Ternary_Heap &Ternary_Heap::operator=(Ternary_Heap &heap)
  224. {
  225.     if (this == &heap)
  226.         return *this;
  227.     if (heap_capacity != heap.heap_capacity)
  228.     {
  229.         delete [] array;
  230.         heap_capacity = heap.heap_capacity;
  231.         array = new int [heap_capacity];
  232.     }
  233.     initial_capacity = heap.initial_capacity;
  234.     heap_size = heap.heap_size;
  235.     for (int i = 0; i < size(); i++)
  236.     {
  237.         array[i] = heap.array[i];
  238.     }
  239.     return *this;
  240. }
  241.  
  242. ostream &operator << (ostream &out, Ternary_Heap &heap)
  243. {
  244.     out << "Size:             " << heap.size() << endl;
  245.     out << "Capacity:         " << heap.capacity() << endl;
  246.     out << "Initial capacity: " << heap.initial_capacity << endl;
  247.     out << "The Heap is:   ";
  248.     for (int i = 0; i < heap.size(); ++i)
  249.     {
  250.         out << heap.array[i] << "   ";
  251.     }
  252.     out << endl;
  253.     return out;
  254. }
  255.  
  256. /*
  257.  * Main Contains Menu
  258.  */
  259. int main()
  260. {
  261.     Ternary_Heap heap(8);
  262.     for (int i = 0; i < N; ++i) 
  263.     {
  264.         int x = (5 + 7 * i) % N;
  265.         heap.push(x);
  266.         cout << heap << endl;
  267.     }
  268.  
  269.     for (int i = 0; i < N; ++i)
  270.     {
  271.         cout << "Current top: " << heap.top() << endl;
  272.         heap.pop();
  273.         cout << heap << endl;
  274.     }
  275.     cout << heap << endl;
  276.     return 0;
  277. }

advertisement
$ g++ ternary_heap.cpp
$ a.out
 
Size:             1
Capacity:         8
Initial capacity: 8
The Heap is:   5
 
Size:             2
Capacity:         8
Initial capacity: 8
The Heap is:   5   12
 
Size:             3
Capacity:         8
Initial capacity: 8
The Heap is:   3   12   5
 
Size:             4
Capacity:         8
Initial capacity: 8
The Heap is:   3   12   5   10
 
Size:             5
Capacity:         8
Initial capacity: 8
The Heap is:   1   3   5   10   12
 
Size:             6
Capacity:         8
Initial capacity: 8
The Heap is:   1   3   5   10   12   8
 
Size:             7
Capacity:         8
Initial capacity: 8
The Heap is:   1   3   5   10   12   8   15
 
Size:             8
Capacity:         8
Initial capacity: 8
The Heap is:   1   3   5   10   12   8   15   6
 
Size:             9
Capacity:         16
Initial capacity: 8
The Heap is:   1   3   5   10   12   8   15   6   13
 
Size:             10
Capacity:         16
Initial capacity: 8
The Heap is:   1   3   4   10   12   8   15   6   13   5
 
Size:             11
Capacity:         16
Initial capacity: 8
The Heap is:   1   3   4   10   12   8   15   6   13   5   11
 
Size:             12
Capacity:         16
Initial capacity: 8
The Heap is:   1   3   4   2   12   8   15   6   13   5   11   10
 
Size:             13
Capacity:         16
Initial capacity: 8
The Heap is:   1   3   4   2   12   8   15   6   13   5   11   10   9
 
Size:             14
Capacity:         16
Initial capacity: 8
The Heap is:   0   1   4   2   3   8   15   6   13   5   11   10   9   12
 
Size:             15
Capacity:         16
Initial capacity: 8
The Heap is:   0   1   4   2   3   8   15   6   13   5   11   10   9   12   7
 
 
Size:             16
Capacity:         16
Initial capacity: 8
The Heap is:   0   1   4   2   3   8   15   6   13   5   11   10   9   12   7   14
 
Current top: 0
Size:             15
Capacity:         16
Initial capacity: 8
The Heap is:   1   3   4   2   7   8   15   6   13   5   11   10   9   12   14
 
 
Current top: 1
Size:             14
Capacity:         16
Initial capacity: 8
The Heap is:   2   3   4   9   7   8   15   6   13   5   11   10   14   12
 
Current top: 2
Size:             13
Capacity:         16
Initial capacity: 8
The Heap is:   3   7   4   9   12   8   15   6   13   5   11   10   14
 
Current top: 3
Size:             12
Capacity:         16
Initial capacity: 8
The Heap is:   4   7   5   9   12   8   15   6   13   14   11   10
 
Current top: 4
Size:             11
Capacity:         16
Initial capacity: 8
The Heap is:   5   7   6   9   12   8   15   10   13   14   11
 
Current top: 5
Size:             10
Capacity:         16
Initial capacity: 8
The Heap is:   6   7   10   9   12   8   15   11   13   14
 
Current top: 6
Size:             9
Capacity:         16
Initial capacity: 8
The Heap is:   7   8   10   9   12   14   15   11   13
 
Current top: 7
Size:             8
Capacity:         16
Initial capacity: 8
The Heap is:   8   12   10   9   13   14   15   11
 
Current top: 8
Size:             7
Capacity:         16
Initial capacity: 8
The Heap is:   9   12   10   11   13   14   15
 
Current top: 9
Size:             6
Capacity:         16
Initial capacity: 8
The Heap is:   10   12   15   11   13   14
 
Current top: 10
Size:             5
Capacity:         16
Initial capacity: 8
The Heap is:   11   12   15   14   13
 
Current top: 11
Size:             4
Capacity:         16
Initial capacity: 8
The Heap is:   12   13   15   14
 
Current top: 12
Size:             3
Capacity:         16
Initial capacity: 8
The Heap is:   13   14   15
 
Current top: 13
Size:             2
Capacity:         16
Initial capacity: 8
The Heap is:   14   15
 
Current top: 14
Size:             1
Capacity:         16
Initial capacity: 8
The Heap is:   15
 
Current top: 15
Size:             0
Capacity:         16
Initial capacity: 8
The Heap is:
 
Size:             0
Capacity:         16
Initial capacity: 8
The Heap is:
 
------------------
(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