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.