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 themaximum. 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.