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