Thread: Need help with C++ min and max heaps.

I've no clue how to build them exactly. Well I kinda do, thanks to code in book. However, I'm not getting the changePriority() thing the teacher recommended. Yes, a heap is a priority queue. The min and max heap should store the same data.

Assignment 3.pdf Assignment 3.pdf

I've tried this much so far:

 
 
 
class MyHeap
{
 
 
class TreeNode
{
 
friend class MyHeap;
 
public:
 
TreeNode(); // stores 0.0 and a pointer to NULL
 
// value is the float value stored correspondingNode is a pointer to the same TreeNode
// inside the other heap tree.
TreeNode(float value, TreeNode *correspondingNode); 
~TreeNode();
void setValue(float value);
float getValue();
void setCorrespondingNode(TreeNode *correspondingNode);
TreeNode getCorrespondingNode() const; // Did I label this one correctly?
 
private:
float value;
TreeNode *correspondingNode;
 
};
 
class MinHeap
{
 
friend class MyHeap;
friend class MaxHeap;
friend class TreeNode;
 
public:
MaxHeap();
~MaxHeap();
 
private:
float *array;
void insert(TreeNode tn);
float deleteMin();
void percolateDown(int value);
void percolateUp(int value);
 
 
};
 
 
class MaxHeap
{
 
friend class MyHeap;
friend class MinHeap;
friend class TreeNode;
 
public:
MinHeap();
~MinHeap();
 
private:
 
float *array;
void insert(TreeNode tn);
float deleteMax();
void percolateDown(int value);
void percolateUp(int value);
};
 
 
 
 
public:
 
MyHeap();
MyHeap(int initialCapacity);
void insert(float f);
float deleteMin();
float deleteMax();
float k_smallest(int k);
 
private:
 
float *minHeapArray;
float *maxHeapArray;
int initialCapacity;
int filledSize;
setFilledSize(int filledSize)
{
this->filledSize = filledSize;
}
 
int getFilledSize()
{
return filledSize;
}
 
 
bool isFull()
{
if (getFilledSize() == initialCapacity)
return true;
return false;
 
}
 
bool isEmpty()
{
if (getFilledSize() == 0)
return true;
return false;
 
}
};

 
#include "MyHeap.h"
#include <iostream>
 
using namespace std;
 
MyHeap::TreeNode::TreeNode()
{
this->value = 0.0f;
this->correspondingNode = NULL;
}
 
MyHeap::TreeNode::TreeNode(float value, TreeNode *correspondingNode)
{
 
this-> value = value;
this-> correspondingNode = correspondingNode;
 
}
 
void MyHeap::TreeNode::setValue(float value)
{
this->value = value;
}
 
float MyHeap::TreeNode::getValue()
{
return value;
}
 
void MyHeap::TreeNode::setCorrespondingNode(TreeNode *correspondingNode)
{
this->correspondingNode = correspondingNode;
}
 
TreeNode MyHeap::TreeNode::getCorrespondingNode() const
{
return correspondingNode;
}
 
MyHeap::MyHeap()
{
minHeap = new float[10];
maxHeap = new float[10];
initialCapacity = 10;
}
 
MyHeap::MyHeap(int initialCapacity)
{
this->initialCapacity = initialCapacity;
minHeap = new float[initialCapacity];
maxHeap = new float[initialCapacity];
}
 
void MyHeap::insert(float f)
{
 
setFilledSize(getFilledSize() + 1);
 
}
 
float MyHeap::deleteMin()
{
 
if (isEmpty())
{
 
cout <<"Cannot delete from empty heap! \n";
 
// Either return NULL or exit program
 
 
}
 
setFilledSize(getFilledSize() -1);
 
}
 
float MyHeap::deleteMax()
{
 
if (isEmpty())
{
 
cout <<"Cannot delete from empty heap! \n";
 
// Either return NULL or exit program
 
 
}
 
setFilledSize(getFilledSize() -1);
 
}
 
float MyHeap::k_smallest(int k)
{
if (isEmpty())
{
 
cout <<"Heap is empty! \n";
 
// Either return NULL or exit program
 
 
}
 
 
}
 
int main()
{
 
}

I can get the percolate down and stuff soon.

The min and max heaps are supposed to contain the same data. How I'd get it to work if it had a value inserted into a max heap and how I'd get it to update the arrays differently and maintain the pointers correctly.

I have the TreeNodes in the MinHeap corresponding to the TreeNodes in the MaxHeap.

Another thought I'm having is that the way I'm going about this is overkill for implementation and I could possibly do it a simpler way, though I can't think of how.

Note: I do realize that I'm allowed to use vectors and might change it to such, though with my last issue with generics, I'm a bit scared to. However, I'd still need to have two vectors of floats.

Note:: The exam is the 17th. That was a typo. Also, deleteMax should remove the maximum . That also was a typo.


The one below should be for a min heap. I'm assuming I can just change the < signs to > signs to have that method for a maxheap, correct?

 
void percolateDown(int hole)
{
 
int child;
 
float tmp = array[hole];
 
for (; hole * 2 <= getFilledSize(); hole = child)
{
child = hole * 2;
if (child != getFilledSize() && array[child+1] < array[child])
child++;
if (array[child] < tmp)
array[hole] = array[child];
else
break;
}
array[hole] = tmp;
}

Ok, the part where I find the kth_smallest(int value). I'm confused on that. Please help with that part first.

Actually, to be frank, I'm rather a data structure, algorithm, and recursion washout. I can get the regular OO stuff well, or well enough, but this stuff takes about 2 to 5 times longer to figure out. Sometimes I don't even have that time to spend on it.

I've got a more specific question. I was wondering, how do you get a pointer to both refer to a value and also to an address?

What I'd love to just do is simply, since my pointers will refer to each other, have it set the value at that address to null or remove the value at that address. However, it would also need to know the value itself, presumably, though maybe not. If that address were to be changed, what would stop it from suddenly pointing to the wrong value?

I've added this new method:

 
TreeNode& MyHeap::TreeNode::getCorrespondingNodeAddress()
{
 
return 
correspondingNode&;
 
}

Is that ok?

Also, I've gotten the idea of making copy constructors for the two different types of heaps. Then I perform remove several times, though I'd have to figure out, in a way that I still have yet to figure out, on the tree that has the root, (Min or Max) closest to the value until I reach that value. Then I remove that from the copy tree and return it (remove actually removes AND returns a value, if you read the assignment specifications.)

But how to destroy the copied tree to free up memory afterward. Not quite sure either. Very new at pointers.

Is there a better way I could go about kth_smallest() then that implementation I suggested above?

How would I do it if so?

As I said earlier, I have an idea how to implement this code, from some stuff the book provided, but I don't know how to use the pointers to change the values when a max is deleted from a min heap. My pointer could, if I knew how to work them correctly, point to the value where that max is at in the min heap. However, I want to go to that address and then then delete it's value and then alter the tree.



It seems that I'd only need to percolate up from that spot. And the book already has a nice method that does it by index.

Still not quite getting it but am starting to, slowly.

Any ideas?

Ok, why does TreeNode not name a type at

TreeNode MyHeap::TreeNode::getCorrespondingNode() const
{
return correspondingNode;
}

Error Message: 'TreeNode' does not name a type

Why not? It should be a valid one?

Also, I've already dealt with the
#ifndef
#define

bla bla bla and a few other mistakes.

Ok, fixed all the bugs so far but now am wondering how to go about insert since I have it as a float but also need to make it call the insert on the corresponding Node so I don't have to call two inserts. That's one of the uses of the TreeNode pointer.

 
#ifndef MY_HEAP_H
#define MY_HEAP_H
 
#include <iostream>
 
using namespace std;
class MyHeap
{
 
 
class TreeNode
{
 
friend class MyHeap;
 
public:
 
TreeNode(); // stores 0.0 and a pointer to NULL
 
// value is the float value stored correspondingNode is a pointer to the same TreeNode
// inside the other heap tree.
TreeNode(float value, TreeNode *correspondingNode); 
~TreeNode();
void setValue(float value);
float getValue();
void setCorrespondingNode(TreeNode *correspondingNode);
TreeNode getCorrespondingNode() 
{
return *correspondingNode;
} // Did I label this one correctly?
 
private:
float value;
TreeNode *correspondingNode;
 
};
 
class MinHeap
{
 
friend class MyHeap;
friend class MaxHeap;
friend class TreeNode;
 
public:
MinHeap();
~MinHeap();
 
private:
float *array;
int filledSize;
void insert(TreeNode tn);
float deleteMin();
void percolateDown(int hole)
{
 
int child;
 
float tmp = array[hole];
 
for (; hole * 2 <= filledSize; hole = child)
{
child = hole * 2;
if (child != filledSize && array[child+1] < array[child])
child++;
if (array[child] < tmp)
array[hole] = array[child];
else
break;
}
array[hole] = tmp;
}
void percolateUp(int value);
 
 
};
 
 
class MaxHeap
{
 
friend class MyHeap;
friend class MinHeap;
friend class TreeNode;
 
public:
MaxHeap();
~MaxHeap();
 
private:
 
float *array;
void insert(float f)
{
 
 
}
int filledSize;
float deleteMax(){
if (filledSize == 0)
{
cout <<"Heap is empty!";
return -1.0f;
 
}
 
float temp = array[1];
array[1] = array[filledSize--];
percolateDown(1);
return temp;
 
}
void percolateDown(int hole)
{
 
int child;
 
float tmp = array[hole];
 
for (; hole * 2 <= filledSize; hole = child)
{
child = hole * 2;
if (child != filledSize && array[child+1] > array[child])
child++;
if (array[child] > tmp)
array[hole] = array[child];
else
break;
}
array[hole] = tmp;
}
void percolateUp(int value);
};
 
 
 
 
public:
 
MyHeap();
MyHeap(int initialCapacity);
void insert(float f);
float deleteMin();
float deleteMax();
float k_smallest(int k);
 
private:
 
float *minHeapArray;
float *maxHeapArray;
int initialCapacity;
int filledSize;
void setFilledSize(int filledSize)
{
this->filledSize = filledSize;
}
 
int getFilledSize()
{
return filledSize;
}
 
 
bool isFull()
{
if (getFilledSize() == initialCapacity)
return true;
return false;
 
}
 
bool isEmpty()
{
if (getFilledSize() == 0)
return true;
return false;
 
}
};
 
#endif

#include "MyHeap.h"
#include <iostream>
 
using namespace std;
 
MyHeap::TreeNode::TreeNode()
{
this->value = 0.0f;
this->correspondingNode = NULL;
}
 
MyHeap::TreeNode::TreeNode(float value, TreeNode *correspondingNode)
{
 
this-> value = value;
this-> correspondingNode = correspondingNode;
 
}
 
 
void MyHeap::TreeNode::setValue(float value)
{
this->value = value;
}
 
float MyHeap::TreeNode::getValue()
{
return value;
}
 
void MyHeap::TreeNode::setCorrespondingNode(TreeNode *correspondingNode)
{
this->correspondingNode = correspondingNode;
}
 
 
 
MyHeap::MyHeap()
{
minHeapArray = new float[10];
maxHeapArray = new float[10];
initialCapacity = 10;
}
 
MyHeap::MyHeap(int initialCapacity)
{
this->initialCapacity = initialCapacity;
minHeapArray = new float[initialCapacity];
maxHeapArray = new float[initialCapacity];
}
 
void MyHeap::insert(float f)
{
 
setFilledSize(getFilledSize() + 1);
 
}
 
float MyHeap::deleteMin()
{
 
if (isEmpty())
{
 
cout <<"Cannot delete from empty heap! \n";
 
// Either return NULL or exit program
 
 
}
 
setFilledSize(getFilledSize() -1);
 
}
 
float MyHeap::deleteMax()
{
 
if (isEmpty())
{
 
cout <<"Cannot delete from empty heap! \n";
 
// Either return NULL or exit program
 
 
}
 
setFilledSize(getFilledSize() -1);
 
}
 
float MyHeap::k_smallest(int k)
{
if (isEmpty())
{
 
cout <<"Heap is empty! \n";
 
// Either return NULL or exit program
 
 
}
 
 
}
 
int main()
{
 
}

It should compile as it did last I checked a few minutes ago.

Could somebody please help me? I've gotten no replies and I've posted days ago. Thanks.

Now it seems I have my array emptying too soon. Also, still need help with the TreeNode pointers so I can find them and use them to update min and max heaps.

 
#ifndef MY_HEAP_H
#define MY_HEAP_H
 
#include <iostream>
 
using namespace std;
class MyHeap
{
 
 
class TreeNode
{
 
friend class MyHeap;
 
public:
 
TreeNode(); // stores 0.0 and a pointer to NULL
 
// value is the float value stored correspondingNode is a pointer to the same TreeNode
// inside the other heap tree.
TreeNode(float value, TreeNode *correspondingNode); 
~TreeNode();
void setValue(float value);
float getValue();
void setCorrespondingNode(TreeNode *correspondingNode);
TreeNode getCorrespondingNode() 
{
return *correspondingNode;
} // Did I label this one correctly?
 
private:
float value;
TreeNode *correspondingNode;
 
};
 
class MinHeap
{
 
friend class MyHeap;
friend class MaxHeap;
friend class TreeNode;
 
public:
MinHeap();
MinHeap(int initialCapacity);
~MinHeap();
 
 
private:
float *array;
int size;
int filledSize;
void insert(float f)
{
if (getFilledSize() == getSize())
{
 
float *array2 = new float[getSize() * 2];
 
for (int i = 0; i < getFilledSize(); i++)
{
array2[i] = array[i];
 
}
 
for (int i = getFilledSize(); i < (getSize() * 2); i++)
{
array2[i] = 0.0f;
}
delete array;
 
array = array2;
 
}
 
setFilledSize(getFilledSize() + 1);
int hole = getFilledSize();
for (; hole > 1 && f < array[hole/2]; hole/=2)
array[hole] = array[hole/2];
array[hole] = f;
 
}
float deleteMin();
 
void setSize(int size)
{
this->size = size;
}
 
int getSize()
{
return size;
}
 
void setFilledSize(int filledSize)
{
this->filledSize = filledSize;
}
 
int getFilledSize()
{
return filledSize;
}
void percolateDown(int hole)
{
 
int child;
 
float tmp = array[hole];
 
for (; hole * 2 <= filledSize; hole = child)
{
child = hole * 2;
if (child != filledSize && array[child+1] < array[child])
child++;
if (array[child] < tmp)
array[hole] = array[child];
else
break;
}
array[hole] = tmp;
}
void percolateUp(int value);
 
 
};
 
 
class MaxHeap
{
 
friend class MyHeap;
friend class MinHeap;
friend class TreeNode;
 
public:
MaxHeap();
MaxHeap(int initialCapacity);
~MaxHeap();
 
 
private:
 
float *array;
void insert(float f);
int filledSize;
int size;
void setFilledSize(int filledSize)
{
this->filledSize = filledSize;
}
 
int getFilledSize()
{
return filledSize;
}
 
void setSize(int size)
{
this->size = size;
}
 
int getSize()
{
return size;
}
 
float deleteMax(){
if (filledSize == 0)
{
cout <<"Heap is empty!";
return -1.0f;
 
}
 
float temp = array[1];
array[1] = array[filledSize--];
percolateDown(1);
return temp;
 
}
void percolateDown(int hole)
{
 
int child;
 
float tmp = array[hole];
 
for (; hole * 2 <= filledSize; hole = child)
{
child = hole * 2;
if (child != filledSize && array[child+1] > array[child])
child++;
if (array[child] > tmp)
array[hole] = array[child];
else
break;
}
array[hole] = tmp;
}
void percolateUp(int value);
};
 
 
 
 
public:
 
MyHeap();
MyHeap(int initialCapacity);
~MyHeap();
void insert(float f);
float deleteMin();
float deleteMax();
float k_smallest(int k);
 
private:
 
MinHeap *minHeap;
MaxHeap *maxHeap;
TreeNode *nodeArray;
int initialCapacity;
int filledSize;
int nodeArraySize;
int filledNodeArraySize;
void setFilledSize(int filledSize)
{
this->filledSize = filledSize;
}
 
int getFilledSize()
{
return filledSize;
}
 
 
bool isFull()
{
if (getFilledSize() == initialCapacity)
return true;
return false;
 
}
 
void setNodeArraySize(int nodeArraySize)
{
this->nodeArraySize = nodeArraySize;
}
 
int getNodeArraySize()
{
return nodeArraySize;
}
 
void setFilledNodeArraySize(int filledNodeArraySize)
{
this->filledNodeArraySize = filledNodeArraySize;
}
 
int getFilledNodeArraySize()
{
return filledNodeArraySize;
}
 
 
 
bool isEmpty()
{
if (getFilledSize() == 0)
return true;
return false;
 
}
};
 
#endif

#include "MyHeap.h"
#include <iostream>
 
using namespace std;
 
MyHeap::TreeNode::TreeNode()
{
this->value = 0.0f;
this->correspondingNode = NULL;
}
 
MyHeap::TreeNode::TreeNode(float value, TreeNode *correspondingNode)
{
 
this-> value = value;
this-> correspondingNode = correspondingNode;
 
}
 
 
void MyHeap::TreeNode::setValue(float value)
{
this->value = value;
}
 
float MyHeap::TreeNode::getValue()
{
return value;
}
 
void MyHeap::TreeNode::setCorrespondingNode(TreeNode *correspondingNode)
{
this->correspondingNode = correspondingNode;
}
 
MyHeap::TreeNode::~TreeNode()
{
delete correspondingNode; // I have a bad feeling this will cause null pointers
}
 
MyHeap::MinHeap::MinHeap(int initialCapacity)
{
array = new float[initialCapacity];
setFilledSize(0);
}
 
MyHeap::MinHeap::MinHeap()
{
array = new float[10];
setFilledSize(0);
}
 
MyHeap::MaxHeap::MaxHeap(int initialCapacity)
{
array = new float[initialCapacity];
 
for (int i =0; i < initialCapacity; i++)
array[i] = 0.0f;
 
setFilledSize(0);
}
 
MyHeap::MaxHeap::MaxHeap()
{
array = new float[10];
 
for (int i =0; i < 10; i++)
array[i] = 0.0f;
 
setFilledSize(0);
}
 
MyHeap::MyHeap()
{
minHeap = new MinHeap(10);
maxHeap = new MaxHeap(10);
nodeArray = new TreeNode[10];
 
initialCapacity = 10;
}
 
MyHeap::MaxHeap::~MaxHeap()
{
delete[] array;
}
 
MyHeap::MinHeap::~MinHeap()
{
delete[] array;
}
 
 
MyHeap::MyHeap(int initialCapacity)
{
this->initialCapacity = initialCapacity;
minHeap = new MinHeap(initialCapacity);
maxHeap = new MaxHeap(initialCapacity);
nodeArray = new TreeNode[initialCapacity];
 
}
 
float MyHeap::MinHeap::deleteMin()
{
if (getFilledSize() == 0)
{
cout <<"Heap is empty!";
return -1.0f;
 
}
float temp = array[1];
array[1] = array[filledSize--];
percolateDown(1);
return temp;
}
 
 
 
 
MyHeap::~MyHeap()
{
delete minHeap;
delete maxHeap;
delete[] nodeArray;
 
}
 
 
 
void MyHeap::insert(float f)
{
 minHeap->insert(f);
 
setFilledSize(getFilledSize() + 1);
// minHeap->setFilledSize(getFilledSize());
// maxHeap->setFilledSize(getFilledSize());
 
}
 
float MyHeap::deleteMin()
{
 
if (isEmpty())
{
 
cout <<"Cannot delete from empty heap! \n";
 
// Either return NULL or exit program
 
 
}
 
 
 
 
 
setFilledSize(getFilledSize() -1);
 return (minHeap->deleteMin());
}
 
float MyHeap::deleteMax()
{
 
if (isEmpty())
{
 
cout <<"Cannot delete from empty heap! \n";
 
// Either return NULL or exit program
 
 
}
 
setFilledSize(getFilledSize() -1);
 
return (maxHeap->deleteMax());
}
 
float MyHeap::k_smallest(int k)
{
if (isEmpty())
{
 
cout <<"Heap is empty! \n";
 
// Either return NULL or exit program
 
 
}
 
 
}
 
int main()
{
 MyHeap mh(15);
 mh.insert(2.0);
 mh.insert(9.0);
cout <<"inserted 2.0";
cout <<mh.deleteMin();
mh.insert(3.0);
cout <<mh.deleteMax();
 
 
}

deleteMax is returning -1 and saying the heap is empty even though it's not.

I have to turn it in. Once again, another project where nobody replied. Thanks everyone for helping me.

I wasn't trolling, just letting out frustration and being sarcastic in the line above.

I think I didn't do that bad on this one actually. Still, I tried politely and tried an SSCCE even, I specified on some specific questions a few times, and no replies. Very discouraging.

Originally Posted by javapenguin

I have to turn it in. Once again, another project where nobody replied. Thanks everyone for helping me.

I wasn't trolling, just letting out frustration and being sarcastic in the line above.

I think I didn't do that bad on this one actually. Still, I tried politely and tried an SSCCE even, I specified on some specific questions a few times, and no replies. Very discouraging.

Nice attitude. Here you have yet again done exactly what you've been told not to do, dozens (or more?) times by now. You have a link to asking questions the smart way in your signature, yet you follow none of the rules it lays out. Then you have the audacity to complain about not getting a reply in a time frame that suits your needs?

Also, this is a Java forum. While we might be able to answer questions about other programming languages, our main focus remains Java. Why don't you post on a C++ forum?

But honestly, with the attitude you've shown, both now and in the past, and your apparent inability to understand simple directions from instructors, assignments, and potential helpers, I seriously think you should reconsider whether programming is really for you.