Piority Queue w/ Ternary Heap

[robert12503]

Folks I am LOST. This is school related but NOT homework. Can someone please tell me what needs to be modified exactly???? Instructions and code are below:

//HERE IS the assignment
Ternary Heaps

Recall the Priority Queues that we implemented with binary heaps. Re-implement the class PriorityQueue, only this time using a ternary heap. A ternary heap is like a binary heap, only every non-leaf node can have up to 3 children. Again, the ternary heap is a complete tree (all levels but the next to last are complete, each node having exactly 3 children) and it should be implemented with an array. The class should provide the same functionality as the PriorityQueue class posted on the notes, namely:

A constructor PriorityQueue(int max_size) and a destructor ~PriorityQueue().
A push(int data), a pop() and a top() method (the pop and top methods should output the least integer in the priority queue). The push and pop methods should both work in logarithmic time, namely the computations in order to push or pop an element should be restricted to just a single path of the tree. Be careful: the tree this time is a ternary tree (each node has 3 children instead of 2) so you should recompute the formulas that provide the indices of the parent and the children of a node.
Overload the << operator so that the user can print the Priority Queue. This method should just print out the array from first to last element (not ordered from min to max).
You can supply your class with as many private methods as you want.
As usual, submit a header file, an implementation file and a test program. You can use variations of the files that you can find online from the lecture notes.

//HERE IS THE ORIGINAL HEADER FILE
#include
using namespace std;

class PriorityQueue {
friend ostream& operator << (ostream& os, PriorityQueue& q);
public:
PriorityQueue(int Max_size);
~PriorityQueue();
void push(int data);
int pop();
int top();
private:
int size;
int elements;
int *storage;
};

//HERE IS ORIGINAL IMPLEMENTATION WITH HEAP
// Implementation with heap: push, pop and top are O(logn)

#include "pqueue.h"

void swap(int* data, int x, int y)
{
int tmp = data[x];
data[x] = data[y];
data[y] = tmp;
}

int min (int* data, int x, int y)
{
if(data[x] <= data[y])
return x;
return y;
}

PriorityQueue::PriorityQueue(int max_size)
{
size = max_size;
elements = 0;
storage = new int[size];
}

PriorityQueue::~PriorityQueue()
{
delete[] storage;
}

void PriorityQueue::push(int data)
{
if (elements == size)
throw "Queue is full";
storage[elements] = data;
elements++;
//Move inserted element in correct position
int child = elements-1, parent = (child-1)/2;
while (parent>=0 && storage[parent] > storage[child]){
swap(storage, parent, child);
child = parent;
parent = (child-1)/2;
}
}

int PriorityQueue::pop()
{
if (elements == 0)
throw "Queue is empty";
int pop_value = storage[0];
storage[0] = storage[--elements];
//fix heap, push top element to correct position
int parent = 0, child1, child2, min_child;
while (2*parent+1<elements){ //while node has children
child1 = 2*parent+1;
child2 = child1+1;
min_child = min(storage, child1, child2);
if (storage[parent] <= storage[min_child])
break;
swap(storage, parent, min_child);
parent = min_child;
}
return pop_value;
}

int PriorityQueue::top()
{
if (elements == 0)
throw "Queue is empty";
return storage[0];
}

ostream& operator<< (ostream &os, PriorityQueue &q)
{
int i;
for(i=0; i
#include "pqueue.h"

int main()
{
int size;
int tmp;
cout << "How many numbers? ";
cin >> size;

PriorityQueue q(size);
int i;

for(i=0; i> tmp;
q.push(tmp);
cout << "Queue is now" << endl;
cout << q;
}

cout << "Sorted sequence" << endl;
for(i=0; i<size; i++)
cout << q.pop() << " ";
cout << endl;

}