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.
/*
* C++ Program to Implement Ternary Heap
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstdlib>
int const N = 16;
using namespace std;
/*
* Ternary Heap Class Declaration
*/
class Ternary_Heap
{
private:
int heap_capacity;
int initial_capacity;
int *array;
int heap_size;
void double_capacity()
{
int *tmp_array = new int[2 * capacity()];
for (int i = 0; i < size(); ++i)
{
tmp_array[i] = array[i];
}
delete [] array;
array = tmp_array;
heap_capacity *= 2;
}
void halve_capacity()
{
int *tmp_array = new int[capacity() / 2];
for (int i = 0; i < size(); ++i)
{
tmp_array[i] = array[i];
}
delete [] array;
array = tmp_array;
heap_capacity /= 2;
}
public:
Ternary_Heap(int);
~Ternary_Heap();
Ternary_Heap(Ternary_Heap &);
Ternary_Heap &operator=(Ternary_Heap &heap);
friend ostream &operator <<(ostream &, Ternary_Heap &);
/*
* Check if Heap is Empty
*/
bool empty()
{
return heap_size == 0;
}
/*
* Return Size of the Heap
*/
int size()
{
return heap_size;
}
/*
* Return Capacity of the Heap
*/
int capacity()
{
return heap_capacity;
}
/*
* Count elements in the Heap
*/
int count(int &obj)
{
int c = 0;
for (int i = 0; i < size(); i++)
{
if (array[i] == obj)
++c;
}
return c;
}
/*
* Returns Top element of the Heap
*/
int top()
{
if (empty())
return NULL;
return array[0];
}
/*
* Push the element into the Heap
*/
void push(int &obj)
{
if (size() == capacity())
double_capacity();
int i = heap_size;
++heap_size;
while (i != 0 && array[(i - 1) / 3] > obj)
{
array[i] = array[(i - 1) / 3];
i = (i - 1) / 3;
}
array[i] = obj;
}
/*
* Remove element from the Heap
*/
void pop()
{
if (empty())
return;
--heap_size;
int last = array[size()];
int posn = 0;
int posn30 = 0;
int posn33 = 3;
while (posn33 < size())
{
int posn31 = posn30 + 1;
int posn32 = posn30 + 2;
int min = last;
int loc = posn;
if (array[posn33] < min)
{
min = array[posn33];
loc = posn33;
}
if (array[posn32] < min)
{
min = array[posn32];
loc = posn32;
}
if (array[posn31] < min)
{
min = array[posn31];
loc = posn31;
}
array[posn] = min;
if (posn == loc)
{
if (4 * size() == capacity())
{
if (capacity() > initial_capacity)
{
halve_capacity();
}
}
return;
}
posn = loc;
posn30 = 3 * loc;
posn33 = posn30 + 3;
}
int min = last;
int loc = posn;
int posn31 = posn30 + 1;
int posn32 = posn30 + 2;
switch (posn33 - size())
{
case 0:
if (array[posn32] < min)
{
min = array[posn32];
loc = posn32;
}
case 1:
if (array[posn31] < min)
{
min = array[posn31];
loc = posn31;
}
}
array[posn] = min;
if (posn != loc)
{
array[loc] = last;
}
}
/*
* Clear Heap
*/
void clear()
{
heap_size = 0;
if (heap_capacity != initial_capacity)
{
heap_capacity = initial_capacity;
delete [] array;
array = new int[heap_capacity];
}
}
};
Ternary_Heap::Ternary_Heap(int n)
{
heap_capacity = max(1, n);
initial_capacity = heap_capacity;
array = new int [heap_capacity];
heap_size = 0;
}
Ternary_Heap::~Ternary_Heap()
{
delete [] array;
}
Ternary_Heap::Ternary_Heap(Ternary_Heap &heap)
{
heap_capacity = heap.heap_capacity;
initial_capacity = heap.initial_capacity;
array = new int [heap_capacity];
heap_size = heap.heap_size;
for (int i = 0; i < heap_size; i++)
{
array[i] = heap.array[i];
}
}
Ternary_Heap &Ternary_Heap::operator=(Ternary_Heap &heap)
{
if (this == &heap)
return *this;
if (heap_capacity != heap.heap_capacity)
{
delete [] array;
heap_capacity = heap.heap_capacity;
array = new int [heap_capacity];
}
initial_capacity = heap.initial_capacity;
heap_size = heap.heap_size;
for (int i = 0; i < size(); i++)
{
array[i] = heap.array[i];
}
return *this;
}
ostream &operator << (ostream &out, Ternary_Heap &heap)
{
out << "Size: " << heap.size() << endl;
out << "Capacity: " << heap.capacity() << endl;
out << "Initial capacity: " << heap.initial_capacity << endl;
out << "The Heap is: ";
for (int i = 0; i < heap.size(); ++i)
{
out << heap.array[i] << " ";
}
out << endl;
return out;
}
/*
* Main Contains Menu
*/
int main()
{
Ternary_Heap heap(8);
for (int i = 0; i < N; ++i)
{
int x = (5 + 7 * i) % N;
heap.push(x);
cout << heap << endl;
}
for (int i = 0; i < N; ++i)
{
cout << "Current top: " << heap.top() << endl;
heap.pop();
cout << heap << endl;
}
cout << heap << endl;
return 0;
}
$ 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.
Related Posts:
- Practice Programming MCQs
- Practice Design & Analysis of Algorithms MCQ
- Practice Computer Science MCQs
- Check Computer Science Books
- Check Data Structure Books