I made a heap that works as a priority queue.

I can make it to work with integers, floats and doubles, but when im using character strings it gives me an error.

Basically my heap uses comparison functions to find out in which order the numbers should be placed. In the comparison function I subtract the left value from the right value to determine where the value should be placed.

In order to use char strings, I use the strcmp function to achieve a similar result to subtracting left to right.

Heres my code(c++)

The main file. Error is all the way at the bottom for you to see

#pragma once
#include <iostream>
#include "Heap.h"
#include <string.h>
using namespace std;


int Compare(int left, int right)
{
	return (left - right);
}

double dCompare(double left, double right)
{
	return (left - right);
}

float fCompare(float left, float right)
{
	return (left - right);
}

int sCompare(char* left, char* right)
{
	return strcmp(left, right);
}



int main()
{
	//Declare a heap with the size of 10
	Heap<int> myHeap(10, Compare);

	//Insert Some items into the heap
	myHeap.Enqueue(1);
	myHeap.Enqueue(2);
	myHeap.Enqueue(3);
	myHeap.Enqueue(10);
	myHeap.Enqueue(12);
	myHeap.Enqueue(4);
	myHeap.Enqueue(8);
	myHeap.Enqueue(100);
	myHeap.Enqueue(87);
	myHeap.Enqueue(99);

	//Now show the items in the heap
	int index;
	for(index = 1; index <= myHeap.m_count; index++)
	{
		cout << myHeap[index] << ", ";
	}

	//Now remove some items from the heap
	myHeap.Dequeue();
	myHeap.Dequeue();
	myHeap.Dequeue();

	//Now show the updated heap
	cout << endl << endl << "Now showing the updated heap:" << endl << endl;
	for(index = 1; index <= myHeap.m_count; index++)
	{
		cout << myHeap[index] << ", ";
	}


	//Create a heap that uses a double instead of a int
    cout << endl << endl << "Creating a double heap" << endl << endl;
	Heap<double> doubleHeap(5, dCompare);
	doubleHeap.Enqueue(5.64);
	doubleHeap.Enqueue(6.37);
	doubleHeap.Enqueue(2.78);
	doubleHeap.Enqueue(1.32);
	doubleHeap.Enqueue(9.51);

	//Show the double heap
	for(int index = 1; index <= doubleHeap.m_count; index++)
	{
		cout << doubleHeap[index] << ", ";
	}

	//Remove some items from the double heap
	doubleHeap.Dequeue();
	doubleHeap.Dequeue();

	//Show the updated double heap
	cout << endl << endl << "Showing the updated double heap" << endl << endl;
	for(int index = 1; index <= doubleHeap.m_count; index++)
	{
		cout << doubleHeap[index] << ", ";
	}


	//Create a float Heap
	Heap<float> floatHeap(5, fCompare);
	floatHeap.Enqueue(20.22f);
	floatHeap.Enqueue(10.11f);
	floatHeap.Enqueue(30.33f);
	floatHeap.Enqueue(50.55f);
	floatHeap.Enqueue(40.44f);

	//Show the float heap
	cout << endl << endl << "The float Heap: " << endl << endl;
	for(int index = 1; index <= floatHeap.m_count; index++)
	{
		cout << floatHeap[index] << ", ";
	}

	//Remove some items from the heap
	floatHeap.Dequeue();
	floatHeap.Dequeue();

	//Show the updated float heap
	cout << endl << endl << "The float Heap: " << endl << endl;
	for(int index = 1; index <= floatHeap.m_count; index++)
	{
		cout << floatHeap[index] << ", ";
	}


	//Create a string heap
	Heap<char> stringHeap(5, sCompare);
	
	

	


	cin.get();
	return 0;
}

the heap class

#pragma once
#include "Array.h"




template <class DataType>
class Heap: public Array<DataType>
{
public:

	//CLASS VARIABLES======================================

	//Keeps track of how many items are in the heap
	int m_count;

	//Function pointer to a comparison function
	DataType (*m_compare)(DataType, DataType);


	//CLASS FUNCTIONS=======================================

	//Constructor: Initializes the array with p_size, and 
	//recieves a pointer to a function
	Heap( int p_size, DataType (*p_compare)(DataType, DataType))
		:Array<DataType>(p_size + 1)
	{
		//Number of items in the heap currently are zero
		m_count = 0;

		//Makes the function pointer point to the passed in pointer
		m_compare = p_compare;
	}


	//Enqueue: Inserts an item into the heap
	void Enqueue(DataType p_data)
	{
		//Updates the counter, to keep track of how many
		//items are in the heap
		m_count++;

		//If the number of entries is larger then the array size
		if(m_count >= m_size)
		{
			//The double the size of the array
			Resize(m_size*2);
		}

		//Inserts the the data in the proper index
		m_array[m_count] = p_data;

		//Perform the WalkUp algorithm to see if the newly inserted
		//item is larger then its parent
		WalkUp(m_count);
	}


	//Dequeue: Removes first/top/root item from the the heap
	void Dequeue()
	{
		//If the heap is not empty
		if(m_count >= 1)
		{
			//Moves the item at the bottom of the heap
			//to the root
			m_array[1] = m_array[m_count];

			//Calls the WalkDown function to align the nodes properly
			// to keep it as a heap
			WalkDown(1);

			//Decrements the number of items in the array
			m_count--;
		}
	}

	//Item: Returns the value at the top of the heap
	DataType& Item()
	{
		return m_array[1];
	}


	//WalkUp: Moves a piece of data upward through the tree, until
	//the tree becomes a valid heap
	void WalkUp(int p_index)
	{
		//The current parent index
		int parent = p_index / 2;

		//The current child index
		int child  = p_index;

		//A temporary variable that holds the data of the child
		DataType temp = m_array[child];

		//While the parent index is not zero
		while(parent > 0)
		{
			//Determines if the node is walking up is in
			//the correct place or not by checking the parent value

			//If the parent node is greater then the node that is being
			//walked up, the function uses the break keyword to quit the loop
		    //If the parent node is less then the node, then the parent
			//node is moved down into the child node, and both the parent 
			//and child pointers are divided by 2, moving them up one level.
			if(m_compare(temp, m_array[parent]) > 0)
			{
				m_array[child] = m_array[parent];
				child = parent;
				parent /= 2;
			}
			else
				break;
		}
		//The data that was supposed to be moved up is moved into the cell
		//that the child points to.
		m_array[child] = temp;
	}

	//WalkDown: Moves the root down the tree until it becomes a heap
	void WalkDown(int p_index)
	{
		//Keeps track of the current parent index
		int parent = p_index;

		//Keeps track of the current child index
		int child = p_index * 2;

		//Stores the data that is being walked down into a temporary variable
		DataType temp = m_array[parent];

		//Starts a loop, loops through the tree until the child index is
		//greater then the tree size
		while(child < m_count)
		{
			//Checks to see if the right child exists
			if(child < m_count - 1)
			{
				//Compares the left and right child to see which one is larger
				
				//             LEFT CHILD       RIGHT CHILD
				if(m_compare(m_array[child], m_array[child + 1]) < 0)
				{
					//If the right child is larger, then increment the child index
					//because the the index of the right child is always is one larger
					//then the left child
					child++;
				}
			}

			//Now the function knows which child it wants to move upward. It
            //Determines if the child node needs to move upward by comparing
			//it to the value in the temp variable

			//If a swap needs to be made
			if(m_compare(temp, m_array[child]) < 0)
			{
				//Moves the child upward into the parent index
				m_array[parent] = m_array[child];

				//Moves the the parent and child index down one level
				parent = child;
				child *= 2;
			}
			//If no swap is needed
			else
				break;
		}
		
		//The value in temp is placed into the correct index
		m_array[parent] = temp;
	}

};


	

and finally the error:

\desktop\heap\heap\example.cpp(122): error C2664: 'Heap<DataType>::Heap(int,DataType (__cdecl *)(DataType,DataType))' : cannot convert parameter 2 from 'int (__cdecl *)(char *,char *)' to 'char (__cdecl *)(char,char)'

1> with

1> [

1> DataType=char

1> ]

1> None of the functions with this name in scope match the target type

I know its saying that it cannot convert, but Im using templates so any datatype can work.

but if I use DataType, it can return an int, whenever the return value is int. The same goes for double and float.

hmmm im not getting something here

Alright I changed my comparison function pointer to using ints only. This way it can read standards ints and char strings but not doubles or floats. How can I let it use any datatype?

A common use case for something like this is to implement the comparison function as a precedence function that returns true if the first operand should precede the second and false if the second operand should precede the first. That way, you can implement compare() without caring what the data type is. Your current functions are implemented this way (if the sign of the subtraction is negative, that indicates the first operand should come before the second) but it does it in a way that the enclosing code needs to know what the data type is, when it really shouldn't have to care.

Not sure I got what your exactly trying to say JTippetts

So far im thinking of using multiple constructors in my class each with its own enqueue/dequeue function

You're over-complicating it.

Look at your code, and the way you use compare().

if(m_compare(temp, m_array[parent]) > 0)
{
   // ...
}
else
{
   // ...
}

You use the return value of compare to determine the ordering of the two elements passed to it. The problem is, the code that calls compare() has to know what the data type is in order to determine that ordering. It has to know, for example, that it can be compared to 0. Why can't you do that comparison inside your compare() function instead? That way, your calling code never has to know what type of data it is acting on. All it has to know is whether or not operand 1 precedes operand 2.

This is the key to creating generic abstract data types. Encapsulate the data as much as you can, so that the algorithms themselves don't have to worry or know or care about what the types are.

Alright I made a comparison function like this:

int trueCompare(int left, int right)
{
	if(left > right)
	{
		return 1;
	}
	if(left < right)
	{
		return -1;
	}
	return 0;
}

lemme see if I can figure out more of this