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.

## All 2 Replies

compiled your code using BCC55 and it does nothing like you claim.

what does happen I quote here:

put 1
MAIN: cmd = put, d = 1
put 2
MAIN: cmd = put, d = 2
put 3
MAIN: cmd = put, d = 3
put 4
MAIN: cmd = put, d = 4
pop
pop
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
ab eterno...

put 4
MAIN: cmd = put, d = 4
put 5
MAIN: cmd = put, d = 5
put 6
MAIN: cmd = put, d = 6
put 7
MAIN: cmd = put, d = 7
pop
pop
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
i = 3
ab eterno

put 1
MAIN: cmd = put, d = 1
put 2
MAIN: cmd = put, d = 2
put 3
MAIN: cmd = put, d = 3
pop
pop
pop returns: 0
MAIN: cmd = pop, d = 4281055
pop returns: 0
MAIN: cmd = pop, d = 4281055
pop returns: 0
MAIN: cmd = pop, d = 4281055
pop returns: 0
MAIN: cmd = pop, d = 4281055
pop returns: 0
MAIN: cmd = pop, d = 4281055
pop returns: 0
MAIN: cmd = pop, d = 4281055
pop returns: 0
MAIN: cmd = pop, d = 4281055
pop returns: 4328364
MAIN: cmd = pop, d = 4281055
pop returns: 4328364
MAIN: cmd = pop, d = 4281055
pop returns: 512
MAIN: cmd = pop, d = 4281055
pop returns: 0
MAIN: cmd = pop, d = 4281055
ab eterno

Sorry for the mix-up but i finally figured the darn thing out. Thanks any way.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.