Comparing strings using a priority queue(heap)

Started by
15 comments, last by Chad Smith 11 years, 2 months ago

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

I think that's a bit overkill, this is more suited for non integral types such as float and double. For integral types, a simple (left - right) like it was originally will do.

Advertisement

^ that's what im trying to do. I want it to work for more than just ints. I still cant get it to work:

Heres what works:

1- Works with ints, doubles and floats but not with strings

2- Works with ints and strings but not doubles or floats

Why not let the user provide the comparison function?

So for char arrays, user would provide the function pointer to strcmp.

For int comparison, user would provide the pointer to int comparison function.

For float comparison, user would provide the pointer to float comparison function.

The function pointer can be passed to the constructor, or as a template arg.

Another alternative is to not use comparison functions, and just user arithmetic comparison operators on left and right. This will require the DataType to have some operators overloaded though.

Works with ints and strings but not doubles or floats

How? There should be one cmp function for each type, so why can't float cmp functions be implemented?

alright im gonna try this tomorrow. Gonna go to sleep lol. Thanks for the ideas people. Ill update this if I get it working

Well Everyone. I got it to work!!!!

What I did was remove the function pointer and made the comparison function built inside the class. The comparison function

just returns bool values so it can work with any datatype now:

Heres the brand new and improved class:


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


template <class DataType>


class Heap2: public Array<DataType>
{
public:

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

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


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


	//Constructor
	Heap2(int p_size)
		: Array<DataType> (p_size + 1)
	{
		m_count = 0;
	}


	//Enqueue
	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)
		{
			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
	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--;
		}
	}


	//WalkUp
	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]) == true)
			{
				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]) == false)
				{
					//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]) == false)
			{
				//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;
	}


	bool m_compare( DataType left, DataType right)
	{
		if(left > right)
			return true;
		if(right > left)
			return false;
		else
		{
			cout << "Critical Failure" << endl;
		}

	}

};


and heres the source file:


#include <iostream>
#include "Heap2.h"
using namespace std;


int main()
{
	//Create a heap and inserts some values into it
	cout << "Inserting ints into the heap..." << endl;
	Heap2<int> myHeap(5);
	myHeap.Enqueue(1);
	myHeap.Enqueue(2);
	myHeap.Enqueue(3);
	myHeap.Enqueue(10);
	myHeap.Enqueue(20);

	//Show the heap on screen
	cout << "Showing the heap: " << endl << endl;
	for(int index = 1; index <= myHeap.m_count; index++)
	{
		cout << myHeap[index] << ", ";
	}
	cout << endl << endl;

	
	//Create a double heap
	cout << "Inserting doubles into the heap..." << endl;
	Heap2<double> dHeap(5);
	dHeap.Enqueue(22.22);
	dHeap.Enqueue(33.33);
	dHeap.Enqueue(44.44);
	dHeap.Enqueue(11.11);
	dHeap.Enqueue(55.55);

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


	//Create a string heap
	cout << "Inserting strings into the heap..." << endl;
	Heap2<char*> sHeap(5);
	sHeap.Enqueue("Hello");
	sHeap.Enqueue("Bye");
	sHeap.Enqueue("Red");
	sHeap.Enqueue("Blue");
	sHeap.Enqueue("Green");

	//Show the string heap on screen
	cout << "Showing the  string heap: " << endl << endl;
	for(int index = 1; index <= sHeap.m_count; index++)
	{
		cout << sHeap[index] << ", ";
	}
	cout << endl << endl;




	cin.get();
	return 0;
}

Thanks to everyone for the input and ideas. Felt like I conquered something lol

Ah, good job. I think there are ways to make it more general, but it's more important to have something working than to have a beautiful piece of art. : )

Good job.

Little nitpick: maybe instead of having the count public, you could make that private then add a function that would return the current size of the Heap. That way the size of the heap couldn't absolutely get modified when it is not supposed to. But I guess you could say that is "preference."

Though it's pretty good! Last year for a class I had to write a heap. Yours turned out A LOT better than mine did. Mine was entirely to dependent on the datatype.

This topic is closed to new replies.

Advertisement