Thread: 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_*/