You are here:

C++/c++heapsort

Advertisement


Question
Write a main program that reads in the data, populating an array and sorts the array (in descending order) using heapsort and prints out the list onto the screen.

The data file which contains the data is of the following format:
S0001 56.9
S0002 444.5
S0003 77
S0004 99
S0005 123.4
S0006 128.8
S0007 33.4

my problem is i nt sure whether i hv implement the function for the sift_up,heapSort and makeHeap is correct anot.i hv to implement the function in tis way,void sift_up(sales *arr,int N),void heapSort(sales *arr, int num),void makeHeap(int node, int num, sales *arr).as for the void printList(sales *arr, int num) i do nt knw hw to implement the function.could u pls help mi,i realli need your help!!pls correct the code if i am wrong.i will be greatly appreciated for all the help from you!!!

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

struct Sales
{
   char id[10];
   float sales;
};

void sift_up(sales *arr,int N);
void heapSort(sales *arr, int num);
void makeHeap(int node, int num, sales *arr);
void printList(sales *arr, int num);

int main()
{

   ifstream inFile;
   
   inFile.open("sales.txt",ios::in);
   
   if (!inFile)
   {
   cerr << "Unable to open file test.txt";
   return 1;
   }
   
   inFile.close();
   system("pause");
   return 0;
}

void sift_up(sales *arr,int N)
{

  while( N != 0 ) {
     int sales = (N+1)/2 - 1;  // n - 1

     if (array[sales] > array[N])
    {
        int tmp = array[N];
        array[N] = array[sales];
        array[sales] = tmp;
        N = sales;
     } else {
        break;
     }
  }
}

void heapSort (sales *arr, int num)
{
   for (int node = num; node >=0; node--)
      makeHeap(node, num, arr);     
}


void makeHeap(int node, int num, sales *arr)
{     
  int curr, child, temp;
  int numlast = (num-2)/2;
  curr = node;
  if (node <= numlast){
     child = 2*node+1;    
     if (sales[node] < value[child])          
        node = child;         
     child++;
     if (child < num && sales[node] < sales[child])          
        node = child;
  }
      if (node != curr)       
   {          
      temp = sales[node];          
      sales[node] = sales[curr];
      sales[curr] = temp;          
      makeHeap(node, num, sales);      
   }
}


Answer
It is much easier to write the function recursively.

struct sales
{
  char id[10];
  float sales;
};

inline int parent( int pos ) { return (pos-1) / 2 ; }

// pos is position of element to sift up
void sift_up( sales* array, int pos )
{
  int parent_pos = parent(pos) ;
  if( array[pos].sales > array[ parent_pos ].sales )
  {
      // swap elements
      sales temp = array[pos] ;
      array[pos] = array[ parent_pos ] ;
      array[ parent_pos ] = temp ;

      // check up the heap for smaller parent
      sift_up( array, parent_pos ) ;
  }
}

// N is array size
void make_heap( sales* array, int N )
{
 for( int i=1 ; i<N ; ++i ) sift_up( array, i ) ;
}

Now, in like fashion, write sift_down, and use it to implement sort_heap.

And you are done; heap_sort is just
a. call make_heap to make a heap
b. then call sort_heap to sort it.

Tutorial help: http://cis.stvincent.edu/html/tutorials/swd/heaps/heaps.html

C++

All Answers


Answers by Expert:


Ask Experts

Volunteer


vijayan

Expertise

my primary areas of interest are generic and template metaprogramming, STL, algorithms, design patterns and c++11. i would not answer questions about gui and web programming.

Experience

about 15 years or so

Education/Credentials
post graduate engineer

©2016 About.com. All rights reserved.