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.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.