I am having a very hard time trying to solve this problem.Here are the instructions to the assignment:
Implement a Priority Queue using a heap.
The heap should be implemented as a class that has a private
member which is an array. The array is statically allocated and
the size of the array is determined by the integer value which is
passed into the (one and only) heap constructor.
Elements are added to the heap via a method called "put" which
receives a single parameter which is the value to insert into
the heap. If the (array inside the) heap is full, a new array
which is twice the size of the existing one will be allocated
and the data elements will be moved to the new array and the
resources of the previous array will be released.
The largest value of the heap (which should, by definition always
reside at index #1) will be returned via a call to the "pop" method
in the heap class. This will reduce the number of elements in the
heap by one, but it is not necessary to ever reduce the size of the
array which is used to store the elements in the heap.
Here is the code I have so far:
#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;
class heap
{
private:
int *array;
public:
int count;
int capacity;
heap(int n)
{
array = new int[n+1];
capacity = n;
count = 0;
}
void put(int d)
{
int *tmparray;
int root=0;
count++;
array[count]=d;
root=array[1];
int i=count;
while(i/2>0 && array[i/2]<array[i]){
int x =0;
array[x]=array[i];
array[i]=array[i/2];
array[i/2]=array[x];
i=i/2;
}
if(count >= capacity){
int k=count;
tmparray=new int [k*2];
for (int j=1;j<=count;j++){
tmparray[j]=array[j];
}
capacity=capacity*2;
delete(array);
array=tmparray;
}
}
int pop()
{
int first = array[1];
int j = 1;
//cout<<"count = " <<count<<endl;
int i=1;
array[i]=array[count];
count--;
//int i=1;
//cout<<"i = " <<i<<endl;
//cout<<"count = " <<count<<endl;
while(i*2+1<=(count*2)+1){
cout<<"i = "<<i<<endl;
if(array[i*2+1]>array[(i*2)]){
int c =0;
array[c]=array[i];
array[i]=array[i*2+1];
array[i*2+1]=array[c];
i++;
}else if(array[i*2]>array[i*2+1]){
int c =0;
array[c]=array[i];
array[i]=array[i*2];
array[i*2]=array[c];
i=i*2;
}
}
// cout<<"after dump = ";dump();
if(count != 0){
return first;
}else{
cout<<"error"<<endl;
return 0;
}
}
void dump()
{
for (int i=1; i<= count; i++) {
cout << " DUMP: node at index [" << i << "] = " << array[i] << endl;
}
cout << endl;
}
};
int main(void)
{
heap myheap(4);
string cmd;
int d;
while (true) {
cin >> cmd >> d;
cout << "MAIN: cmd = " << cmd << ", d = " << d << endl;
if (cmd == "put") {
myheap.put(d);
} else if (cmd == "pop") {
int i = myheap.pop();
cout << "pop returns: " << i << endl;
} else if (cmd == "dump")
myheap.dump();
else if (cmd == "quit")
exit(0);
}
}My put function works fine. It is the pop method I am have trouble with.
When I have 4 nodes in the tree it will pop them off and dump out the nodes in the correct order. When I have more than 4 nodes it does not dump them out in the correct order plus I lose one node somewhere and it replaces it with another node.
