Archive for the ‘C / C++’ Category

Static in c – hide that function

Tuesday, July 13th, 2010

In the c language there is no such thing as a class, private/public setup as such, but if you have a allot of c files that may have allot of the same function names inside e.g. swap(void *data, void *data2). So how do you just want to call your swap function and not another one from another c file. Which in this setup it is similar to private method within a class.

So instead of having access to the private keyword, you can define a function to be a static function as below in this header file that I have called static_test.h

#ifndef STATIC_TEST_H
#define STATIC_TEST_H
 
#include <iostream>
using namespace std;
 
static void PrivateAccessable(char *sting);
 
void PublicAccessable(char *st);
 
#endif // STATIC_TEST_H

the PublicAccessable function is what is *exposed* to other parts of the main program but the static void PrivateAccesable is not.

So if you try and access it via the int main function like so

 
#include <iostream>
#include "static_test.h"
 
int main(int argc, char *argv[])
{
 
    PublicAccessable("hi there");
    // undefined reference to `PrivateAccessable(char*)'
    PrivateAccessable("should not be able to access this!!");
 
    return 0;
}

The compiler will complain with something similar to the error above the PrivateAccessable line, or

undefined reference to `PrivateAccessable(char*)'

because the linker does not know where that function is, since it is “hidden” within the static_test namespace as such.

Just to complete the code example here is the static_test.c

#include "static_test.h"
 
static void PrivateAccessable(char *sting)
{
    cout << sting << endl;
}
 
void PublicAccessable(char *st)
{
    PrivateAccessable(st);
}

Graphs – Part 2

Wednesday, July 7th, 2010

The graphs use two algorithms to either find the shortest path (Dijkstra algorithm) or the minimal spanning tree (Krushal’s method).

This is the second post of the assignment of the Path class and also the Dijkstra / Krushal methods. So to start with the Path class, below is the header of the class with the different methods inside the class, which basically has a Add method to add the arc to the Path, TotalPathDistance which will return the total distance taken in O(1) in big O notation, a toString method which returns a string version of the internal data structure of the arcs added, size method which returns the size of the arcs added to the arcs internal vector array and lastly the GetElementAt method that will return a arc of a element at any given point in the vector array.

class Path {
 
// [TODO: complete the class definition]
 
public:
	Path();
	~Path();
 
/*
 * Function: Add
 * Usage: Add(arcT *arc);
 * ----------------------------------
 * Adds a arc to the internal array of arc(s)
 */
	void Add(arcT *arc);
 
/*
 * Function: TotalPathDistance
 * Usage: TotalPathDistance();
 * ----------------------------------
 * returns the total distance in a O(1) time instead of cycling through the list of arcs
 */
	double TotalPathDistance();
 
 
/*
 * Function: toString
 * Usage: toString();
 * ----------------------------------
 * converts the array of arcs to a string repenstation
 */
	string toString();
 
/*
 * Function: size
 * Usage: size();
 * ----------------------------------
 * returns the size of the internal arcs implemetation e.g. the total amount of arcs already stored.
 */
	int size();
/*
 * Function: GetElementAt
 * Usage: GetElementAt(4);
 * ----------------------------------
 * returns a arcT* at any given element index, as passed by the parameter
 */
	arcT* GetElementAt(int i);
 
private:
	Vector<arcT *> arcs;
	double totalCost;
};

and here is the functions implementation, to start with the Path class is constructed with a total distance of 0 and then every time that a new arc is added the total distance is increased by the value of the cost associated with that arc. The tostring method just loops over the vector array of arcs and builds up a string of there details.

Path::Path()
{
	totalCost = 0;
}
 
Path::~Path()
{
	arcs.clear();
}
 
void Path::Add(arcT *arc)
{
	arcs.add(arc);
	totalCost += arc->cost;
}
 
double Path::TotalPathDistance()
{
	return totalCost;
}
 
string Path::toString()
{
	string returnStr;
	foreach(arcT *arc in arcs)
	{
		returnStr = returnStr + arc->start->name + "->" + arc->finish->name + "(" + RealToString(arc->cost) + ")" +"\n";
	}
	return returnStr;
}
 
int Path::size()
{
	return arcs.size();
}
 
arcT* Path::GetElementAt(int i)
{
	return arcs[i];
}

Because the Dijkstra method was already coded from the course reader handout, here is how I have altered it to use the new Path class to have a big O notation of O(1), I have just basically altered it where it was a Vector types to be a Path type instead and called the relevant methods on that new Path type instead of using the TotalPathDistance function, also with a couple of changes to the bottom part of the function below because there was no = operator, so instead changed to GetElementAt method.

Path FindShortestPath(nodeT *start, nodeT *finish) {
	Path path;
	PQueue< Path> queue;
	Map<double> fixed;
	while (start != finish) {
		if (!fixed.containsKey(start->name)) {
			fixed.put(start->name, path.TotalPathDistance());  
			foreach (arcT *arc in start->arcs) {
				if (!fixed.containsKey(arc->finish->name)) {
					Path newPath = path;
					newPath.Add(arc);
					queue.add(newPath, newPath.TotalPathDistance());
				}
			}
		}
		if (queue.isEmpty()) return Path();
		path = queue.extractMin();
		start = path.GetElementAt(path.size() -1)->finish; 
	}
	return path;
}

and here is the Kruskal function, to start with I only need to store the set of nodes within a array (so using a vector array) with also the just needing to store the arcs that are joining the nodes together (I am using a Set here instead of a vector, but does not really matter as such). So to start with I am first building up a list of nodes (Vector array of Sets of strings) of each node within the graph, whilst also adding to a priority queue of all of the arcs, I could have used a foreach loop and gone over the getNodesSet from thePath variable, but the arcs should have all of the nodes inside it :), and since if the nodes are not attached to the arcs then how could they form a path!. And then the main loop is just going through all of the arcs in order of cost (lowest first to highest) seeing if the start and finish nodes are within the same Set within the vector array, if so they have already been added to the minimal spanning tree (Kruskal) else if they have not been added merge (union) the two sets together and also add the arc to the list of arcs to display to the screen once this function has completed.

void KruskalMethod(PathfinderGraph &thePath)
{
	Set<arcT *> arcs = thePath.getArcSet();
	PQueue<arcT *> path;
	Vector< Set<string> > nodes;
	Set<arcT *> theJoiningArcs;
 
	CleanScreen(thePath);
	// place into a pqueue and also build up a vector of sets of the different node names
	foreach (arcT *arc in arcs)
	{
		path.add(arc, arc->cost);
		bool inAlready = false;
		for (int i = 0; i < nodes.size(); i++)
		{
			if (nodes[i].contains(arc->start->name))
			{
				inAlready = true;
				break;
			}
		}
		if (!inAlready)
		{
			Set<string> newNode;
			newNode.add(arc->start->name);
			nodes.add(newNode);
		}
	}
	while (!path.isEmpty())
	{
		arcT * arc = path.extractMin();
		// start node and end nodes set id
		int startN, endN;
		startN = endN = -1;
		for (int i =0; i < nodes.size(); i++)
		{
			if (nodes[i].contains(arc->start->name))
				startN = i;
			if (nodes[i].contains(arc->finish->name))
				endN = i;
		}
		// if in different sets then
		if (startN != endN)
		{
			nodes[startN].unionWith(nodes[endN]);
			nodes.removeAt(endN);
			theJoiningArcs.add(arc);
//			cout << "Cost : " << arc->cost << " : Start : " << arc->start->name << " : Finish : " << arc->finish->name << endl;
		} /*else
			cout << "Cost : " << arc->cost << " : Start : " << arc->start->name << " : Finish : " << arc->finish->name << " ( not needed) " << endl;*/
	}
	// draw out all of the arcs on the grid in a dim color
	DrawNodes(thePath.getNodeSet(), DIM_COLOR);	
	// draw the minimum arcs in a highlight color
	DrawArcs(theJoiningArcs, HIGHLIGHT_COLOR);
}

Graphs

Wednesday, July 7th, 2010

The graphs use two algorithms to either find the shortest path (Dijkstra algorithm) or the minimal spanning tree (Krushal’s method).

I am going to split up the assignment into 2 posts so that can try and covert as much of the assignment without spanning a massive post, so in this post going to talk about loading in the data from the textual files and also displaying the data on screen (graphics), and how I altered the sublcass to allow for more data to be stored for this assignment. In the next post it will be about the Path class implementation with the Dijkstra and Krushal algorithms.

So to start off with, I altered the type definition for the main/parent class of Graph to be called PathfinderGraphMain so that when I created the subclass I could call it the PathfinderGraph, just liked the look of that :). and since the graph types, nodeT / arcT are capable of holding all of the other data (have included them in the code below) I just need to store the graph image which is what the subclass below is doing for me, was trying to avoid using any global variables, so that is all that my subclass is additional storing and accessing using the get/set functions.

typedef Graph<nodeT, arcT> PathfinderGraphMain;
class PathfinderGraph : public PathfinderGraphMain
{
public:
	string returnJpg() { return jpgimage;}
	void setJpg(string jpg) { jpgimage = jpg;}
 
private:
	string jpgimage;
};
 
// as taken from the graphtypes.h
struct nodeT {
	string name;
	Set<arcT *> arcs;
	pointT loc;
};
struct arcT {
	nodeT *start, *finish;
	double cost;
};

here is the sub part of the method that will read in the data from the textual file, I am basically reading in the nodes to start with and then calling the AddNode function (below the code) and also the AddArc (again further down in the code below) which basically just call the main Graph class addNode / addArc functions.

if (contents=="NODES")
	{
		// end at EOF or ARCS
		while (contents != "ARCS" && !inFile.eof())
		{
			contents = ReadLineFromFile(inFile);
			// add the node into 
			if (contents != "ARCS")
			{
				// need to split the contents string
				pointT location;
				int nameI = contents.find_first_of(" ");
				location.x = StringToInteger(contents.substr(nameI, contents.find_last_of(" ")- nameI));
				location.y = StringToInteger(contents.substr(contents.find_last_of(" ")));
				AddNode(contents.substr(0,nameI), location, thePath);
			}
		}
	}
	// end point is the word ARCS
	if (contents == "ARCS")
	{
		// read till the end
		while (!inFile.eof())
		{
			contents = ReadLineFromFile(inFile);
			if (!inFile.eof())
			{
				string startP, endP;
				int nameI = contents.find_first_of(" ");
				startP = contents.substr(0, nameI);
				nameI++;
				endP = contents.substr(nameI, contents.find_last_of(" ")-nameI);
				double cost = StringToReal(contents.substr(contents.find_last_of(" ")));
				AddArc(startP, endP, cost, thePath);
			}
		}
	}
 
void AddNode(string name, pointT location, PathfinderGraph &thePath)
{
	nodeT *node = new nodeT();
	node->name = name;
	node->loc = location;
	thePath.addNode(node);
}
 
void AddArc(string startP, string endP, double cost, PathfinderGraph &thePath)
{
	nodeT *start = thePath.getNode(startP);
	nodeT *end = thePath.getNode(endP);
 
	arcT *arc = new arcT();
	arc->cost = cost;
	arc->start = start;
	arc->finish = end;
	thePath.addArc(arc);
 
	arcT *arc2 = new arcT();
	arc2->cost = cost;
	arc2->start = end;
	arc2->finish = start;
	thePath.addArc(arc2);
}

To draw to the screen, I have created two methods that will take a set of nodes (nodeT structures) and also the colour that is required to display. Since the Set class has a Iterator I can use the foreach (marco from the CS106B libraries) to loop over the Set class to then just display the nodes/arcs via the CS106B graphics libraries again.

void DrawNodes(Set<nodeT *> nodes, string color)
{	
	foreach (nodeT *node in nodes)
	{
		DrawPathfinderNode(node->loc, color, node->name);
		DrawArcs(node->arcs, color);
	}
	UpdatePathfinderDisplay();
}
 
void DrawArcs(Set<arcT *> arcs, string color)
{
	foreach (arcT *arc in arcs)
		DrawPathfinderArc(arc->start->loc, arc->finish->loc, color);
}

The last part of the graphical aspects is getting the mouse inputs to link to a node on the graphical display, once again using the CS106B libraries for obtaining a point location (x/y coordinates) and then testing to see if this coordinates have clicked on the node location (kinder putting a square around the node of the node radius in size, this NODE_RADIUS is defined in the CS106B libraries and that is what the node will have a circle radius off)

// find the nodes near the mouse cords
// NULL if not found a node, else return a nodeT
nodeT * GetNodeFromMouseCords(PathfinderGraph &thePath, pointT mouseInput)
{
	nodeT * returnNode;
	foreach (nodeT *node in thePath.getNodeSet())
	{
		pointT location = node->loc;
		if (mouseInput.x >(location.x - NODE_RADIUS) && 
			mouseInput.x <(location.x + NODE_RADIUS))
			if (mouseInput.y > (location.y - NODE_RADIUS) &&
				mouseInput.y < (location.y + NODE_RADIUS))
				return node;
	}
	return NULL;
}
 
// need to pull out two places, start and end.
void GetTwoLocationsFromMouse(PathfinderGraph &thePath, nodeT * &startN, nodeT * &finishN)
{
	pointT mouseClick = pointT();
	cout << "Please choice your starting location "<< endl;
	while ((startN = GetNodeFromMouseCords(thePath, mouseClick)) == NULL)
		mouseClick = GetMouseClick();
	cout << "Start : " << startN->name << endl;
	DrawPathfinderNode(startN->loc, HIGHLIGHT_COLOR, startN->name);
	while (true)
	{
		cout << "Please choice your ending location "<< endl;
		mouseClick = pointT();
		while ((finishN = GetNodeFromMouseCords(thePath, mouseClick)) == NULL)
			mouseClick = GetMouseClick();
		if (startN->name == finishN->name)
			cout << "That is silly, you are already there!"<< endl;
		else
			break;
	}
	cout << "Finish : " << finishN->name << endl;
	DrawPathfinderNode(finishN->loc, HIGHLIGHT_COLOR, finishN->name);
}

after the user has selected two nodes it will highlight the nodes with the HIGHLIGHT_COLOR from the CS106B libraries again (which was the colour red). I shall post next on the Path class and also the two breath-search and minimal spanning trees, (Dijkstra and Krushal’s algorithms).

Huffman coding – part 2

Thursday, July 1st, 2010

The huffman coding is mainly used to compress files that are not already compressed already ( the reason why I say this for is because if you are trying to compress a already compressed file then the assignment 5 will add on more header details onto the file for decompressing the compressed file.

This is a follow on from the part 1 of the assignment 5 this is the decompression of the compressed file.

So to start with, I need to read in the header file of the compressed file. For example if I was going to compress the file

hello there

then the compressed file will be

104=2|101=3|108=2|111=1|32=1|116=1|114=1|-1=1|;u

Huffman coding – part 1

Thursday, July 1st, 2010

The huffman coding is mainly used to compress files that are not already compressed already ( the reason why I say this for is because if you are trying to compress a already compressed file then the assignment 5 will add on more header details onto the file for decompressing the compressed file.

The basics of this assignment, I have included the assignment PDF to the attached file, is to read in the file and place the characters that are read in (1 character at a time) into a mapped of characters that have there associated value of how many times that there are present in the file, so that the most present characters in the file will end up with a very short bit patten in the compressed file (this is how the file will be smaller, e.g. less space taken up on the disk per character within the file) lets say that there is a sentence of “hi there”, then e will be the most used value e.g. 2, so a character is allot bitter in a bit pattern (to store all of the available characters e.g. a-z, smiles etc.) than a bit patten of 2 in length (01) if that was the case.

So to get started this post is going to be doing the compression of the file, and the second post will be the decompression of the file.

Here is how I am reading in that mapped of characters to there occurrences in the file, theMap is a vector of queueI structure, so that we know that will always have the same values inserted into a vector array, thus when it comes to decompressing the file we want to build up the huffman encoding with the same input values.

   struct queueI {
	   int letter;
	   int value;
   };
 
void Encoding::readFile(ibstream &inStream)
{
	theMap.clear();
	char *readIn = new char(1);
	int i;
	queueI insert;
	while (!inStream.eof())
	{
		inStream.read(readIn,1);
		if (!inStream.eof())
		{
			for (i = 0; i < theMap.size(); i++)
			{
				if (theMap[i].letter == readIn[0]) 
					break;
			}
			if (i < theMap.size())
				theMap[i].value++;
			else
			{
				insert.letter = readIn[0];
				insert.value = 1;
				theMap.add(insert);
			}
		}
	}
	// add the EOF
	insert.letter = PSEUDOEOF;
	insert.value = 1;
	theMap.add(insert);
	delete readIn;
}

The last value is the end of file, a pseudo value that will denote that we have reached the end of file value, I then will need to build up a queue(as taken from the last assignment 4 of this course) of the values taken in from the build of theMap above, so to start with I just load all of the values into queue with there order value (value equals the number of occurrences that they are present in the file) and this is how I am loading the values into the queue.

void Encoding::loadPQueue()
{
	theQueue.clear();
	queueT *qt;
	for (int i =0 ; i < theMap.size(); i++)
	{
		qt = new queueT();
		qt->letter = theMap[i].letter; 
		qt->value = theMap[i].value;
		qt->left = NULL;
		qt->right = NULL;
		qt->filled = true;
		theQueue.add(qt, theMap[i].value);
	}	
}

and here is how I build up the huffman encoding list, what it does is to take the lowest two values (the lowest two occurrences, or later on the lowest two joined values) and put them together with a new node that points to them both and takes the value of both of the values added together, so lets say that the character a has a value of 2 and the letter c has the value of 3, then the new node will have a value of 5 and points to both the characters a,c on the left/rights nodes accordlying.

void Encoding::buildTree()
{
	queueT *newQ, *first, *second;
	int valueIn;
	while (!theQueue.isEmpty())
	{
		newQ = new queueT();
		first = theQueue.extractMin();
		valueIn =first->value;
		newQ->left = first;
		if (!theQueue.isEmpty())
		{
			second = theQueue.extractMin();
			valueIn += second->value;
			newQ->right = second;
		}
		newQ->value = valueIn;
		newQ->filled = false;
		if (!theQueue.isEmpty())
			theQueue.add(newQ, valueIn);
	}
	theQueue.add(newQ, valueIn);
}

right that the main part done!, since when we decompress the file we want to have the same order of the loading into the queue we need to write out the header details to the new decompressed file,

void Encoding::outHeaderToFile(obstream &outStream)
{
	string outStr;
	for (int i =0; i < theMap.size(); i++)
	{
		outStr = IntegerToString(theMap[i].letter);
		outStr +="=";
		outStr += IntegerToString(theMap[i].value);
		outStr +="|";
		outStream.write(outStr.c_str(),outStr.length());	
	}
	// end of header details
	outStr = ";";
	outStream.write(outStr.c_str(), 1);
}

the ; is the end of the header details, thus after that we will write out the bit patterns of the compressed characters :). the output of the header details is the character code=number of occurrences so for character a with 10 occurrences then it would output 97=10|

So since we now need to write out the bit patterns of the characters to the file, we need to find out how we placed those characters into the huffman tree, so I wrote a recursive function that will output the bit pattern of where the character is in the huffman tree

string Encoding::printQueue(queueT *node, int letter,string val)
{
	string returnVal;
	if (node != NULL)
	{
		if (node->left != NULL)
		{
			returnVal = printQueue(node->left, letter, val+"0");
			if (returnVal != "")
				return returnVal;
		}
		if (node->filled)
			if (node->letter == letter)
				return val;
		if (node->right != NULL)
		{
			returnVal = printQueue(node->right, letter, val+"1");
			if (returnVal != "")
				return returnVal;
		}
	}
	return "";
}

If we are heading down the left node, then add a 0 to the bit pattern, if we have found the character and it is classed as a filled node (e.g. only nodes that have a character attached to them are filled) then return how we found that character, or try the right node with adding a 1 to the bit pattern.

Then to just write out the uncompressed file to the compressed file we just go through the file again and then write out all of the bit patterns with ending with the pseudo EOF character.

void Encoding::outToFile(ibstream &inStream, obstream &outStream)
{
	queueT *head;
	string foundStr;
	char *readIn = new char(2);
	while (!inStream.eof())
	{
		inStream.read(readIn,1);
		if (!inStream.eof())
		{
			head = theQueue.peek();
			foundStr = printQueue(head, readIn[0], "");
			for (int i =0; i < foundStr.length(); i++)
			{
				int ch = ((int)foundStr[i])-48;
				outStream.writebit(ch);
			}
		}
	}
	// add in the pseudo-EOF
	head = theQueue.peek();
	foundStr = printQueue(head,PSEUDOEOF, "");
	for (int i =0; i < foundStr.length(); i++)
	{
		int ch = ((int)foundStr[i])-48;
		outStream.writebit(ch);
	}
}

that is about it, I shall do a post on how I do the uncompress-ion next.

Copying values and not content

Tuesday, June 22nd, 2010

Copying values from one variable to another is very common place and the fun starts when you start to copy the pointer address and not the actual memory associated with that address, so lets say that we have a structure with a pointer to some memory, as below

struct testCell {
       int normalInt;
       int *values;
};

then we are capable of assigning the values to both the normalInt value and also creating a place in memory for values or let it point to somewhere in memory (copy of another value ? / array etc), but it is just a pointer to memory somewhere (hopefully not NULL !!)

So if we did something like

testCell t1;
t1.normalInt = 10;
t1.values = new int(3);

all is good, the normalInt value is 10 and also the values has a new integer value of 3 from the heap memory storage space, the problem being here is that when you copy a * (pointer) variable you copy the address and not the actual memory, so if you did something like

testCell t2;
t2 = t1;

t2 will have the value of 10 in normalInt and also the values of 3 (dereferenced of course), but if you did not deference the values variable and just outputted it you would find out that the t1.values and the t2.values are the same, e.g. pointing to the same place in memory and this could have major problems if you to delete t1.values or t1 went out of scope and the compile reclaimed memory that t1 was using, thus t2.values would not be a good memory storage!!, errors would be a massive problem.

The code below demonstrates this with having the t1.values being a array and the t2 variable setting a value within the t2.values and thus altering t1.values as well.

#include <iostream>
 
using namespace std;
 
struct testCell {
       int normalInt;
       int *values;
};
 
int main()
{
   testCell test1;
   test1.values = new int[10];
       for (int i =0; i < 10; i++)
               test1.values[i] = i;
 
       cout  << "normal values of test1" << endl;
       for (int i =0; i < 10; i++)
               cout << "i " << i << "  " << test1.values[i] << endl;
 
   testCell test2 = test1;
 
       cout << "but since we copied the values of what was inside the test1 " << endl;
       cout << "then test2 values value is the same as test1 e.g. the same
pointer to memory" << endl;
       test2.values[3] = 77;
       for (int i =0; i < 10; i++)
               cout << "i " << i << "  " << test1.values[i] << endl;
 
       cout << "test 1 values value " << test1.values << endl;
       cout << "test 2 values value (the same ) " << test2.values << endl;
 
       cout << "so test 2 is actually altering the same values within test 1
!!! ERROR PROBLEMS" << endl;
       delete test1.values;
       return 0;
}

here would be the output, and as you can see the memory locations of t1.values and t2.values are the same!!!..

normal values of test1
i 0  0
i 1  1
i 2  2
i 3  3
i 4  4
i 5  5
i 6  6
i 7  7
i 8  8
i 9  9
but since we copied the values of what was inside the test1
then test2 values value is the same as test1 e.g. the same pointer to memory
i 0  0
i 1  1
i 2  2
i 3  77
i 4  4
i 5  5
i 6  6
i 7  7
i 8  8
i 9  9
test 1 values value 0xab7010
test 2 values value (the same ) 0xab7010
so test 2 is actually altering the same values within test 1 !!! ERROR PROBLEMS

Priority queues

Monday, June 21st, 2010

This is all about priority queue problems with using different techniques for storing the data in a queue, the priority queue could be similar to a queue in a hospital ER ward where the people with the biggest of problems are treated first. I am finding all of the computer science course at Stanford really interesting.

But a heap implementation is similar to a binary tree where the top node is the lowest value and the further you go down each part of the tree you will find higher and higher values. As you can see the below picture, but the main thing is that the highest values may be associated on another place compared to the next highest value, but when you remove the minimum value then you place the last node from the tree to the top node and then move that down to where it should be.

Heap storage

CS106B Assignment 4 Part 2

So to insert the values, I am using a recursive funciton

void PQueue::insertValue(int heapInsert)
{
	int newElemI = heapInsert;
	// need to find out if the parent value
	if (heapInsert > 0)
	{
		// decrement the heapInsert since we start from 0.
		heapInsert--;
		// if we are at the top then make it check with the top
		if (heapInsert == 1) 
			heapInsert=0; 
		else // else goto the parent node
			heapInsert/=2;
		// if parent node is greater than the present node, then swap and go up
		if (heapValues[(heapInsert)] > heapValues[newElemI])
		{
			// swap values
			swapValues((heapInsert), newElemI);
			return insertValue(heapInsert);
		}
	}
	return;
}

where it will call itself if a swap happens e.g the parent node is higher in value than the present node that we are checking, and the way that it works out the parent node is to divide the heapInsert by 2, but of course the top 3 nodes that is a special condition and also since arrays start from 0, then we have to — (-1) from the heapinsert value to start with. The newElemI is where we are at present.

To remove the top element, we need to remove that element and replace with the last node from the array, but then move this value down into the tree depending on if the value is less higher than the lowest value beneath it, so once again I did a recursive method that will call itself if a swap occurs, we just need to test the lower left/right elements first to find the lowest value and then check against that with the parent value and if so, swap.

void PQueue::moveRootDown(int rootID)
{
	// test to see which one of the lower two are the smallest of values
	int leftValue = (rootID*2);
	int rightValue = (rootID*2)+1;
	int smallest =-1;
	if (leftValue <= heapUsedSize)
		smallest = leftValue;
	if (rightValue <= heapUsedSize)
		if (heapValues[smallest-1] > heapValues[rightValue-1])
			smallest = rightValue;
	if (smallest == -1) return;
	if (heapValues[rootID-1] > heapValues[smallest-1])
	{
		swapValues(rootID-1, smallest-1);
		moveRootDown(smallest);
	}
}

that was the main aspects again of the assignment and here is the full source code, I have included the source code and the assignment PDF file in the zip file attached

#include "pqueue.h"
#include "genlib.h"
#include <iostream>
 
/* 
heap implementation
*/
 
const int heapStart = 10;
 
PQueue::PQueue()
{
	heapSize = heapStart;
	heapValues = new int[heapStart];
	heapUsedSize = 0;
}
 
PQueue::~PQueue()
{
	delete[] heapValues;
}
 
bool PQueue::isEmpty()
{
	if (heapUsedSize == 0)
		return true;
	else
		return false;
}
 
int PQueue::size()
{
	return heapUsedSize;
}
 
void PQueue::add(int newElem)
{
	// if we are the max then double
	if (heapSize == heapUsedSize)
		doubleCapacity();
	heapValues[heapUsedSize] = newElem;
	insertValue(heapUsedSize);
	heapUsedSize++;
}
 
// newElemI = index value of the new insert
void PQueue::insertValue(int heapInsert)
{
	int newElemI = heapInsert;
	// need to find out if the parent value
	if (heapInsert > 0)
	{
		// decrement the heapInsert since we start from 0.
		heapInsert--;
		// if we are at the top then make it check with the top
		if (heapInsert == 1) 
			heapInsert=0; 
		else // else goto the parent node
			heapInsert/=2;
		// if parent node is greater than the present node, then swap and go up
		if (heapValues[(heapInsert)] > heapValues[newElemI])
		{
			// swap values
			swapValues((heapInsert), newElemI);
			return insertValue(heapInsert);
		}
	}
	return;
}
 
void PQueue::swapValues(int swap1, int swap2)
{
	int tmp = heapValues[swap1];
	heapValues[swap1] = heapValues[swap2];
	heapValues[swap2] = tmp;
}
 
void PQueue::printOut()
{
	for (int i =0; i < heapUsedSize; i++)
		cout << "i " << i  << "   " << heapValues[i] << endl;
}
 
// double the capacity of the heap size
void PQueue::doubleCapacity()
{
	int *temp = new int[heapSize*2];
	for (int i =0; i < heapSize; i++)
		temp[i] = heapValues[i];
	delete[] heapValues;
	heapValues = temp;
	heapSize *=2;
}
 
int PQueue::extractMin()
{
	if (isEmpty())
		Error("no more values");
	else
	{
		int returnValue = heapValues[0];
		heapUsedSize--;
		heapValues[0] = heapValues[heapUsedSize];
		moveRootDown(1);
		return returnValue;
	}
	return 0;
}
 
void PQueue::moveRootDown(int rootID)
{
	// test to see which one of the lower two are the smallest of values
	int leftValue = (rootID*2);
	int rightValue = (rootID*2)+1;
	int smallest =-1;
	if (leftValue <= heapUsedSize)
		smallest = leftValue;
	if (rightValue <= heapUsedSize)
		if (heapValues[smallest-1] > heapValues[rightValue-1])
			smallest = rightValue;
	if (smallest == -1) return;
	if (heapValues[rootID-1] > heapValues[smallest-1])
	{
		swapValues(rootID-1, smallest-1);
		moveRootDown(smallest);
	}
}

here is what I added to the header file for the private aspects of the class.

    // heap size = the total amount of size 
    // heap used size = the amount of used space in the heap size
    // heap values = the actual values within the heap
    int heapSize, heapUsedSize;
    int *heapValues;
 
    void doubleCapacity();
	void printOut();
	void insertValue(int heapInsert);
	void swapValues(int swap1, int swap2);
	void moveRootDown(int rootID);