We help IT Professionals succeed at work.

We've partnered with Certified Experts, Carl Webster and Richard Faulkner, to bring you two Citrix podcasts. Learn about 2020 trends and get answers to your biggest Citrix questions!Listen Now

x

# Heap Sort   NEED HELP

on
Medium Priority
1,016 Views
Hi Experts,

I really need your help.  I do not understand how to create this heap sort in ascending order.  Ok heres the problem I am opening a file that contains random numbers here they are: file d1: {28      -647      -382        69       895      -655       404
-546     -9      -749      -831      -220      -444      -263       966        71
531       293       534       560       646      -695       251      -369
-305       834        40      -197       213       571       863       739
733       349       517       164      -220      -288      -598       654
-167       -72       958      -746      -573       916       475      -181
560       516       913      -942      -361       514      -513       179
-912       912      -361      -880      -115       830       144      -761
139      -495        -7      -525       -45      -187       746      -145
-282      -235      -912      -677        45       393      -804      -197
547      -509      -313      -539      -403      -390       774      -925
302      -202       352       465       875      -532       677       934
557      -136       348       618}

those are the numbers but not that important.  I have them inserted into a vector array already but cannot sort them using heap sort in ascending order.

I am using a template class EX: template<class T, class U>

the U is for the predicate: less<int>(x,y) you can see this in the example program.

At this moment all I can get sorted is the very least number.

for example: { -942 then all the other 99 numbers randomly printed}

Any help would be greatly appreciated!!!

Here is the program :

********************************************************

#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <functional>
#include <iterator>
#include <stack>
#include <stdexcept>
using namespace std;

#define D1 "D:/heap.d1"

#define INT_SZ 4    // width of integer
#define FLT_SZ 7    // width of floating-pt number
#define STR_SZ 12   // width of string

#define INT_LN 15   // no of integers on single line
#define FLT_LN 9    // no of floating-pt nums on single line
#define STR_LN 5    // no of strings on single line

// function prototypes

template<class T,class U> void insert(vector<T>&, const T&, U);
template<class T,class U> T remove(vector<T>&, U);

template<class T,class U> void upheap(vector<T>&, int, U);
template<class T,class U> void downheap(vector<T>&, int, U);

template<class T,class U>
void get_list(vector<T>&, const char*, U);

template<class T,class U>
void print_list(vector<T>&, const int, const int, U);

int main()
{
vector<int>    v1(1);   // heap of integers
vector<float>  v2(1);   // heap of floating-pt nums
vector<string> v3(1);   // heap of strings

// sort and print first list

cout << "first list - ascending order:\n\n";
get_list(v1, D1, less<int>());
print_list(v1, INT_SZ, INT_LN, less<int>());

cout << "\t\t\t*** end of program execution ***\n\n";

return 0;
}

template<class T,class U>
void get_list(vector<T>& heap, const char*filename, U pred)
{
T item;

fstream infile(filename);

while(infile >> item)
{
insert(heap, item, pred);

}

}

template<class T,class U>
void insert(vector<T>& heap, const T& item, U pred)
{

heap.push_back(item);

upheap(heap, item, pred);

}

template<class T,class U>
void upheap(vector<T>& heap, int item, U pred)
{
int i = 1;
int j = 1;
int temp;
//T left_child[i] = 2 * i;
//T right_child[i] = 2 * i + 1;

int heap_size = heap.size();
for(int a = 0; a <= 100; a++)
{
if (pred(heap[i], heap[j]))
{
swap(heap[i],heap[j]);
}

i++;
}

}

template<class T,class U>
void print_list(vector<T>& heap, const int int_s, const int int_l, U pred)
{

int heapsize = heap.size();

for(int i = 1; i < heapsize; i++)
{
cout << heap[i] << endl;
}

}

Comment
Watch Question

## View Solution Only

Commented:
Is this an academic exercise? If not, have you considered using the standard library heap sort functions? See example in  http://www.sgi.com/tech/stl/sort_heap.html

Commented:
It's a non-credit course I'm taking on the side to help me in certain areas of my job.  I havn't had a whole lot of c++ in training or career.  With this program I have never used a predicate or a function like this before, so it has me a little confused.

I'm trying to write it with out the STL(with the STL I know I could write the whole thing in just 5 lines)

So if you have any suggestions on how to move the item up the tree I would appreciate it.

Thanks again.
Commented:
your problem lies in the upheap function

template<class T,class U>
void upheap(vector<T>& heap, int item, U pred)
{
int i = 1;
int j = 1;
int temp;
//T left_child[i] = 2 * i;
//T right_child[i] = 2 * i + 1;

int heap_size = heap.size();
for(int a = 0; a <= 100; a++)
{
if (pred(heap[i], heap[j]))
{
swap(heap[i],heap[j]);
}
i++;
}
}
a few hints:
- you are skipping comparison with heap[0]
- you are making comparisons with uninitialized contents of heap, i.e. beyond and including heap.size()
- there are a few unused variables in the function.

you are also missing the critical step of sorting between populating the heap and printing it. see http://en.wikipedia.org/wiki/Heap_sort for details. and here's a quick summary.
- create a max heap; your current implementation attempts to create a min heap
now the sorting part:
- remove the max element, adjust the heap so it maintains its properties
- append the max element and exclude it from further iterations
keep repeating until the heap is empty. do not use heap.empty() to test this condition as there will be elements in the heap vector<int> but not in the mental heap that you are supposed to imagine.
see the animation to get an idea of how shifting of elements is supposed to be done.

if you do not care about maintaining contents of heap after printing, you can create a min heap and throw away extracted values after you print them. see http://en.wikipedia.org/wiki/Min_heap

Not the solution you were looking for? Getting a personalized solution is easy.

Commented:
Look at http://sig9.com/articles/sorting-algorithms.

There is a very detailed description of what a heap sort does.

The main point is to find the max (or the min) of the set, swap it to the end (or begin). Then repeat it excluding the max (min) position which is already correct.

The following main function implements a test prog for the functions of the above article. You may port it to your template class and change from max heap to min heap.

Regards, Alex

#include <iostream>
#include <iomanip>
using namespace std;

void display(const char* p, int a[], int r, int b)
{
cout << setw(3) << left << p;
for (int i = 0; i <= b; ++i)
if (i < r)
cout << "   ";
else
cout << setw(3) << setfill(' ') << a[i];
cout << endl;
}

int main()
{
int a[] = {  8, 6, 10, 3, 1, 2,  5,  4, };
int s   = sizeof(a)/sizeof(int);
display("m:", a, 0, s-1);
heapsort(a, s);
display("m:", a, 0, s-1);
return 0;
}

##### Thanks for using Experts Exchange.

• View three pieces of content (articles, solutions, posts, and videos)
• Ask the experts questions (counted toward content limit)
• Customize your dashboard and profile