Solved

Heap Sort   NEED HELP

Posted on 2006-10-28
4
993 Views
Last Modified: 2008-01-09
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;
      }       
      
}

      
0
Comment
Question by:nothing8171
4 Comments
 
LVL 17

Expert Comment

by:rstaveley
Comment Utility
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
0
 
LVL 1

Author Comment

by:nothing8171
Comment Utility
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.
0
 
LVL 9

Accepted Solution

by:
jhshukla earned 500 total points
Comment Utility
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
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
Comment Utility
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;
}


0

Featured Post

How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

Join & Write a Comment

Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

771 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now