Heap Program Help

I'm pretty much done with a program that sorts a list of ints using a heap via a vector but the program will not print the results and I can't figure out whats wrong. Heres the code I have. Thanks.

Code:

#include "heap.h"
#include <iostream>

/***********************************************************
File name:    driver.cpp
Date:         4/16/08
Developed by: 
Description:  Tests the int heap.
************************************************************/
/* 2 item
   1 item
   already sorted list
   random list
   reverse order list  
 */

int main(){
	
	Heap h;
	list<int> l;
	
	//for(int i = 10; i!=0; i--)
		//l.push_back(i);

	l.push_back(5);
	l.push_back(3);
	l.push_back(2);
	l.push_back(4);
	l.push_back(1);

	h.heap_sort(l,h);
	
	for(int i=0; i<(int)l.size();i++)
	{
		cout<< l.back()<<"\n";
		l.pop_back();
	}
	
	
	return 0;
}

Code:

/***********************************************************
File name:    heap.cpp
Date:         4/16/08
Developed by: 
Description:  Creates a heap using a complete binary tree.
************************************************************/

#include "heap.h"
#include <iostream>

int Heap::removeHeapRoot(){
	
	CompTree::Position r = t.root();
	CompTree::Position last = t.last();
	t.swap(r, last);
	
	int root = t.remove();
	int currentRank = t.root().rank;

	
	CompTree::Position n = CompTree::Position(currentRank,&t.v);

	//while(t.v.at(currentRank)> t.v.at(currentRank*2) || t.v.at(currentRank)> t.v.at(currentRank*2+1)){         
		//t.isInternal(CompTree::Position(currentRank,&(t.v)));
	
	while(t.isInternal(n)){	
		if(t.v.at(currentRank)> t.v.at(currentRank*2))
		{
			CompTree::Position a = CompTree::Position(currentRank,&t.v);
			CompTree::Position b = CompTree::Position(currentRank*2,&t.v);
			
			t.swap(a,b);
			currentRank *=2;
		}
		else if(t.v.at(currentRank)> t.v.at(currentRank*2+1))
		{	
			CompTree::Position c = CompTree::Position(currentRank,&t.v);
		    CompTree::Position d = CompTree::Position(currentRank*2+1,&t.v);
		    
		    t.swap(c,d);
			currentRank = currentRank*2+1;
		}

		CompTree::Position n = CompTree::Position(currentRank,&t.v); //to update loop gaurd.
	} 
	
	return root;
}

CompTree::Position Heap::insert(int x){
	t.add(x);
	int currentRank = t.last().rank;
	
	while(t.v.at(currentRank) < t.v.at((int)floor(currentRank/2))){    
		
		CompTree::Position a = CompTree::Position(currentRank,&t.v);
	    CompTree::Position b = CompTree::Position((int)floor(currentRank/2),&t.v);
	
	    t.swap(a,b);
		currentRank = (int)floor(currentRank/2);
     }
	return CompTree::Position(currentRank,&t.v);
}

int Heap::size(){
	return t.size();
}

bool Heap::isEmpty(){
	return t.isEmpty();
}

void Heap::heap_sort(list<int> &l, Heap &h){
	
	for(int i=0; i<(int)l.size();i++)
	{
		h.insert(l.front());
		l.pop_front();
	}
	
	for(int i=0; i< h.size(); i++)
	{
		l.push_back(h.removeHeapRoot());
	}
	
}

Code:

#ifndef HEAP_H_
#define HEAP_H_

/***********************************************************
File name:    heap.h
Date:         4/16/08
Developed by: 
Description:  Creates a heap using a complete binary tree.
************************************************************/

#include "compTree.h"
#include <list>

class Heap{
public:
	int removeHeapRoot(); //swap last than bubble down
	CompTree::Position insert(int x); //add last than bubble up
	int size(); //return compTree.size
	bool isEmpty();
	void heap_sort(list<int> &s, Heap &h);

	CompTree t;
};
#endif /*HEAP_H_*/

Code:

/***********************************************************
File name:    compTree.cpp
Date:         4/16/08
Developed by: 
Description:  Creates a binary tree using a vector.
************************************************************/

#include "compTree.h"


CompTree::CompTree(){
	v.push_back(-1);  //set rank 0 to null because the root of the tree starts at rank 1
}

CompTree::Position CompTree::add(int x){
	v.push_back(x);
	return last();
}

int CompTree::remove(){
	int temp = v.back();
	v.pop_back();
	return temp;
}

int CompTree::removeRoot(){
	v[1]=last().element();
	return remove();
}

CompTree::Position CompTree::last(){
	if(!isEmpty())
		return Position(v.size()-1,&v);
	else return Position(-1, &v);
}

CompTree::Position CompTree::root(){
	if(!isEmpty())
		return Position(1,&v);
	else return Position(-1, &v);
}

CompTree::Position CompTree::leftChild(Position &p){
	if(!isEmpty())
		return Position(p.rank*2 ,&v);
	else return Position(-1, &v);
}

CompTree::Position CompTree::rightChild(Position &p){
	if(!isEmpty())
			return Position(p.rank*2+1 ,&v);
	else return Position(-1, &v);
}

CompTree::Position CompTree::sibling(Position &p){
	int temp = parent(p).rank;
	if(v.at((int)floor(temp/2))== p.element())
		return Position((int)floor(temp/2+1),&v);
	else
		return Position((int)floor(temp/2),&v);
}

CompTree::Position CompTree::parent(Position &p){
	return Position((int)floor(p.rank/2) ,&v);
}

bool CompTree::isInternal(Position &p){
	int temp = (int)floor(p.rank*2);
		if ((int)v.size()>= temp)
			return true;
		else
			return false;
}

bool CompTree::isExternal(Position &p){
	int temp = (int)floor(p.rank*2);
	if ((int)v.size()>= temp)
		return false;
	else
		return true;
}	

bool CompTree::isEmpty(){
	if(v.at(1) != -1)
		return false;
	else
		return true;
}

void CompTree::swap(Position &p1, Position &p2){
	int temp = p1.element();
	p1.ptr->at(p1.rank) = p2.element();
	p2.ptr->at(p2.rank) = temp;
}

int CompTree::size(){
	return v.size()-1; //because v[0] is not considered part of the tree.
}

CompTree::~CompTree(){};

CompTree::Position::Position(int r, vector<int> *vp){
	rank = r; 
	ptr = vp;
}

int CompTree::Position::element(){
	return ptr->at(rank);
}

bool CompTree::Position::isNull(){
	if(rank == -1)
		return true;
	else
		return false;
}
CompTree::Position::~Position(){}

Code:

#ifndef COMPTREE_H_
#define COMPTREE_H_

/***********************************************************
File name:    compTree.h
Date:         4/16/08
Developed by: 
Description:  Creates a binary tree using a vector.
************************************************************/

#include <vector>
#include <math.h>

using namespace std;


class CompTree {
public:
	class Position;
	
	vector<int> v;
	
	CompTree();
	Position add(int x);
	Position last();
	Position root();
	Position leftChild(Position &p);
	Position rightChild(Position &p);
	Position sibling(Position &p);
	Position parent(Position &p);
	int remove();
	int removeRoot();
	bool isInternal(Position &p);
	bool isExternal(Position &p);
	bool isEmpty();
	void swap(Position &p1, Position &p2);
	int size();
	~CompTree();
	
	
	
	class Position {
	public:
		Position(int r, vector<int> *vp);
		int element();
		bool isNull();
		int rank;
		vector<int> *ptr;
		~Position();
	};
		
};
#endif /*COMPTREE2_H_*/

Unfortunately I cannot compile it: it says all the floor calls are ambigous. However, isn't simple integer division good enough: 5/2 = 2 etc?
If I remove floor, it throws an exception (out-of-bounds access from at).

The whole thing is rather complicated (a bit too much? Why does the Heap::heap_sort need to take a Heap parameter if it is *this anyway?).

A few things I noticed:

Code:

bool CompTree::isEmpty(){
	if(v.at(1) != -1)
		return false;
	else
		return true;
}

Why should this show that the CompTree is empty? Did you mean index 1? Do you intend to change the unused item (-1) at index 0?

Code:

void Heap::heap_sort(list<int> &l, Heap &h){
	for(int i=0; i<(int)l.size();i++)
	{
		h.insert(l.front());
		l.pop_front();
	}
        ...

This doesn't read everything in the list: the index gets equal to the size when you have read half the list.
Try something like:

Code:

while (!l.empty()) {
     h.insert(l.front);
     l.pop_front();
}

Try and remember to replace your tabs with the expected number of spaces prior to posting your code.

Don't use floor on an int! All that does is takes an integer, which as you should know is already a whole number, converts that to a double (which of course also will be a whole number since that's what it was created from). Then it passes that through the floor function, which will have zero effect, then you need to convert it back to an int. The conversions both ways are slow, particularly the conversion back to int. When sorting a large array you'd probably get quite a substantial speed decrease because of it.

If you move the "position" declaration to the top of CompTree to replace the forward declaration then you wont need to write an empty destructor, you will be able to leave it out. I'm not really sure what your Position class does for you anyway. It looks to me like it just adds complexity. I'd recommend getting rid of it entirely.

If you're going to write functions like leftChild, rightChild, and parent, then why don't you use these from within your other functions as appropriate?

Do you need "isInternal" and "isExternal"? It doesn't look like they provide any useful functionality to me. If you do need them then surely one could simply call the other and return the negation of the result. Otherwise you're effectively writing the same function twice. If there was a bug you'd have two bugs to fix instead of one.

"last" isn't a useful heap operation yet you expose it as a public function of the class. Since it's only used within removeRoot, you may as well just copy the code to inside there and delete this function altogether.

These loops are a very strange way of doing things:

Code:

	for(int i=0; i<(int)l.size();i++)
	{
		h.insert(l.front());
		l.pop_front();
	}
	
	for(int i=0; i< h.size(); i++)
	{
		l.push_back(h.removeHeapRoot());
	}

First of all, instead of casting the result of size you could change the type of i to match instead; no cast and no warning. Secondly, have you realised that every loop iteration, not only does i increase, but the size decreases? So if you have 5 items, once you've removed the 3rd item, i is 2, and the size of the list is 2 and the loop stops even though it hasn't finished removing items from the list.
What you should be doing is simply using a while loop with while (!l.empty())
The same goes for the loop that comes after it. You don't care how many items there are and you don't need to count them, you just want to keep going until there are no more.

5 items in reverse order is not a useful test. Try it with 1000 randomly generated items. Also try it with only one item, and with zero items. Any good sorting algorithm wont fall over simply because your data set happens to be empty.

I'll leave it there for now, it's getting late.

Thanks guys, your exactly right about the for loops being wrong. I changed them all to while(!empty). As for the Position class I have to use it because the assignment requires me to use it. I changed the isEmpty() to

Code:

bool CompTree::isEmpty(){
	if(v.size() == 1)
		return true;
	else
		return false;
}

v[0] should be set to -1 in the CompTree construtor. Does any know why this program will not print the sorted list in the driver class? Thanks a lot.

Originally Posted by Rob4226

Thanks guys, your exactly right about the for loops being wrong. I changed them all to while(!empty). As for the Position class I have to use it because the assignment requires me to use it. I changed the isEmpty() to

Code:

bool CompTree::isEmpty(){
	if(v.size() == 1)
		return true;
	else
		return false;
}

v[0] should be set to -1 in the CompTree construtor. Does any know why this program will not print the sorted list in the driver class? Thanks a lot.

Ah that makes sense, 'Position' looked like possibly something that you could be required to use.

The printing loop suffers from the same problem as the other loops. An example of normal code that iterates over a list is:

Code:

for (std::list<int>:iterator it = myList.begin(); it != myList.end(); ++it)
    cout << *it << endl;

The problem isn't that the window is closing before you can read the results is it? If so, read the FAQ.

So this will not work?

Code:

while(!l.empty())
{
   cout<< l.back()<<"\n"; 
   l.pop_back();
}

For one thing, you are accessing vector items with at(). This is supposed to throw an exception if the index is out of bounds. So, in main() you might try catching it, so you know what is going wrong.

Another thing I noticed:

Code:

    CompTree::Position n = CompTree::Position(currentRank,&t.v);
   //...
    while(t.isInternal(n)){
       //...
       CompTree::Position n = CompTree::Position(currentRank,&t.v); //to update loop gaurd.
   }

This is not quite doing what the comment says.

Another thing:

Code:

bool CompTree::isInternal(Position &p){
	int temp = p.rank*2;  //removed floor
		if ((int)v.size() >= temp)
			return true;
		else
			return false;
}

After this test you are happily accessing index temp and temp + 1 which can both be out of bounds.

Also

Code:

bool CompTree::isExternal(Position &p){
	int temp = p.rank*2;
	if ((int)v.size()>= temp)
		return false;
	else
		return true;
}

It seems that there are case where both isInternal and isExternal can return true.

I can't comment on the correctness of the algorithm. RemoveRoot could be implemented in ~10-20 lines of code, so I don't really see if all the helper functions and classes are necessary...

As to clearing the list - why? The size of the list won't change, so you could iterate over the list once, inserting items into the heap, then iterate again, assigning the top back to each item.

Thanks for everyones help but I doubt I will ever get this program to work right its already 2 days late and I can't waste any more time on it because im falling behind in my other classes. My professor expects us to learn a brand new languge(C++) as well as these data structures. The class is called Data Structures but I had no idea I would have to learn a brand new language. If it was in Java like it was supposed to be I would have been done in 1 day but I don't know C++ well enough to trouble shoot errors like I can in Java. But thanks again for everyones time.

Why don't you write (and debug) a prototype in Java then (and keep it simple )? Once you are finished you can translate that to C++ - I would imagine that the difference would be only in syntax.

Alright I got an extension of time from my professor and I think the problem is somewhere in the removeHeapRoot method. Anon what exactly do you mean the the loop guard update isnt doing what the comment says? I think thats part of the problem. And I fixed the internal and external methods to:

Code:

bool CompTree::isInternal(Position &p){
	cout<<"isInternal\n";
	if(isExternal(p))
		return false;
	else
		return true;
		
}

bool CompTree::isExternal(Position &p){
	int temp = (int)floor(p.rank*2);
	if (size()> temp)
		return false;
	else
		return true;
}

Originally Posted by Rob4226

Alright I got an extension of time from my professor and I think the problem is somewhere in the removeHeapRoot method. Anon what exactly do you mean the the loop guard update isnt doing what the comment says? I think thats part of the problem. And I fixed the internal and external methods to:

Code:

bool CompTree::isInternal(Position &p){
	cout<<"isInternal\n";
	if(isExternal(p))
		return false;
	else
		return true;
		
}

bool CompTree::isExternal(Position &p){
	int temp = (int)floor(p.rank*2);
	if (size()> temp)
		return false;
	else
		return true;
}

You're starting to catch on. You're still falling short on a few things though.
For starters you've still got that 'floor' in there. As I said before the ONLY thing it does is slow your program down.

You haven't learned negation? isExternal already returns a boolean. Nevermind several lines of an if-statement, you just want to negate the result. Here's a one line isExternal function body:

Code:

 	return !isExternal(p);

While we're at it, here's a one line isExternal function body

Code:

	return size() <= p.rank*2;

Oh and here's a one-line isEmpty function body:

Code:

	return v.size() == 1;

As you can see you're writing far more code than you need to. I'm barely scratching the surface here.

Yes this will work:

Code:

while(!l.empty())
{
   cout<< l.back()<<"\n"; 
   l.pop_back();
}

But why would you ever write it that way? What if you wanted to output the list and then do something else with it and then perhaps output it again? Don't destroy it just to observe it's contents - it's not a quantum list!

Something tells me that you don't know Java as well as you think you do, otherwise I'm sure you'd be applying most of the same techniques here that I've just shown.

After making the current lot of changes I think you need to post an updated version of your code so we can see where you're at.

Originally Posted by Rob4226

Alright I got an extension of time from my professor and I think the problem is somewhere in the removeHeapRoot method. Anon what exactly do you mean the the loop guard update isnt doing what the comment says?

The bold red part is a variable declaration. You declare another object n which shadows the previous n that you use to control the loop. The n that is used in the while condition is never modified in the loop.

Like this:

Code:

#include <iostream>

int main()
{
    int a = 5;
    std::cout << a << '\n';  //5
    {
        int a = 12; //shadows a in outer scope
        std::cout << a << '\n';  //12
    }   //everything declared between the braces goes out of scope
    std::cout << a << '\n';  //5, original a is available again
}

I think thats part of the problem. And I fixed the internal and external methods to:

Ok, this checks that index*2 is in range, but if I'm not mistaken, in removeRoot you access index*2 + 1 without any further checks.

You can put your entire main in a try block:

Code:

#include <exception>

int main()
{
    try {
        Heap h;
        ...
    }
    catch (std::exception& e) {
        std::cout << e.what() << '\n';
    }
}

This way you'll know if you are still having out-of-bounds vector accesses.

The bold red part is a variable declaration. You declare another object n which shadows the previous n that you use to control the loop. The n that is used in the while condition is never modified in the loop.

Ok that makes sense. How do I update that variable? Thanks

Code:

/*CompTree::Position*/ n = CompTree::Position(currentRank,&t.v); //to update loop gaurd.

Like this?

Ok, I am getting very close. I get this input/output I get but its not exactly right I can't see where the error is.

input: 5 3 2 4 1 9 7 11 200
output: 1 2 5 4 7 9 11 3 200

Code:

#include "heap.h"
#include <iostream>

int Heap::removeHeapRoot(){
	
	CompTree::Position r = t.root();
	CompTree::Position last = t.last();
	t.swap(r, last);
	
	int root = t.remove();
	int currentRank = t.root().rank;

	
	CompTree::Position n = CompTree::Position(currentRank,&t.v);

	//while(t.v.at(currentRank)> t.v.at(currentRank*2) || t.v.at(currentRank)> t.v.at(currentRank*2+1)){         
		//t.isInternal(CompTree::Position(currentRank,&(t.v)));
	
	while(t.isInternal(n)){	
		//cout<<"while loop of removeHeapRoot\n";
		if(currentRank+1<=size()){
		if(t.v.at(currentRank)> t.v.at(currentRank*2))
		{
			CompTree::Position a = CompTree::Position(currentRank,&t.v);
			CompTree::Position b = CompTree::Position(currentRank*2,&t.v);
			
			t.swap(a,b);
			currentRank *=2;
			//cout<<"swap parent with left child\n";
		}
		else if(t.v.at(currentRank)> t.v.at(currentRank*2+1))
		{	
			CompTree::Position c = CompTree::Position(currentRank,&t.v);
		    CompTree::Position d = CompTree::Position(currentRank*2+1,&t.v);
		    
		    t.swap(c,d);
			currentRank = currentRank*2+1;
			//cout<<"swap parent with right child\n";
		}
		else
			break;
		}
		else
			cout<<"doesnt work\n";
		 n = CompTree::Position(currentRank,&t.v); //to update loop gaurd.
	} 
	//cout<<"should return root";
	return root;
}

CompTree::Position Heap::insert(int x){
	t.add(x);
	int currentRank = t.last().rank;
	
	while(t.v.at(currentRank) < t.v.at((int)floor(currentRank/2))){    
	
		CompTree::Position a = CompTree::Position(currentRank,&t.v);
	    CompTree::Position b = CompTree::Position((int)floor(currentRank/2),&t.v);
	
	    t.swap(a,b);
		currentRank = (int)floor(currentRank/2);
     }
	return CompTree::Position(currentRank,&t.v);
}

void Heap::heap_sort(list<int> &l, Heap &h){
	
	while (!l.empty()) {
	     h.insert(l.front());
	     cout<<l.front()<<"\n";
	     l.pop_front();
	}
	
	while(!h.isEmpty())
	{
		//cout<<"size"<<h.size()<<"\n";
		cout<< "root " <<h.t.root().element()<<"\n";
		l.push_back(h.removeHeapRoot());
		//cout<<"size"<<h.size()<<"\n";
	}
	
}