Heapsort is not modular

Question

For the time being, I am not interested in any recursive solution. The code is not modularized; the whole body is inside the main function.

#include<iostream.h>
#include<stdlib.h>
/*This code is written by NF between any time of 120711 and 210711;modified at 231211*/

int main()
{
    int length=0,min_heapified=0,start_length=0,index=0;
    cout<<"Enter Array Length:";
    cin>>length;
    int array[length];
    for(int i=0;i<length;i++)
    {
        array[i]=rand()%100;
    }
    cout<<"Array is filled now with random elements";
    cout<<"\nSorted Array:"<<endl;
    do
    {       
            do
            {
                min_heapified=0;
                for(int root=0;root<length/2;root++)/*As the leaf nodes have no child they should not be in a consideration while swapping so looping upto length/2 is enough*/
                {

                    int left=((2*root)+1);
                    int right=((2*root)+2);

                    if(left<length)
                    {
                           if(array[left]<array[root])
                           {
                                int swap=array[left];
                                array[left]=array[root];
                                array[root]=swap;
                                min_heapified=1;    
                           }
                     }
                    if(right<length)
                     {
                            if(array[right]<array[root])
                            {
                                 int swap=array[right];
                                 array[right]=array[root];
                                 array[root]=swap;
                                 min_heapified=1;    
                             }
                      }

                  }

             }while(min_heapified>0);

            int swap=array[0];
            array[0]=array[--length];/*modification done at this point to avoid keeping the sorted elements into another array;and swapping done between the 0th and last element*/
            array[length]=swap;
            cout<<array[length]<<" "; 

 }while(length>0);

  return 0;

}

Answer 1

The other answers cover the stylistic concerns of your code pretty well already. However, there is still one major issue with your code that warrants another (albeit late)answer: it's incorrectly implemented!

The "heapsort" algorithm that you implemented has a run-time complexity of O(N²). Judging from your comment, you probably realized something was wrong too since the run-time sky-rocketed as you tried to sort more items.

Here are the problem areas I see that's causing the abysmal performance:

• You are re-heapifying the entire array on each iteration. This is of course completely wrong and it's the biggest reason why your code is performing so poorly. You're only suppose to heapify the array once, at the beginning when you start the sort.
• Shifting all the elements down by one after removing the smallest. This is an O(N) operation that can be avoided altogether with a redesign.
• Use of a temp array -- this is also unnecessary. Like quicksort, one of heapsort's advantages is that it's capable of sorting in-place without the need to allocate a temporary buffer.
• Heapifying 'leaf' elements needlessly. By definition, leaf elements don't have any child nodes below them so there's nothing to push down. Therefore, it doesn't make sense to heapify pass the last parent element. In other words, you should be going from root = 0 to root < (length / 2). Going pass length / 2 will just result in unnecessary comparisons: left < length and right < length will always be false.

It's typical to write 2 helper functions when implementing heapsort: heapify that turns the array into a heap, and a push_down or filter_down function to enforce the heap property for the element passed in. You usually implement heapify with the help of the filter function.

Note that the stl has heap functions that does exactly those tasks: push_heap, pop_heap and make_heap.

I'll leave the utility functions for you to figure out but here's how the top view of heapsort should look:

void heapsort(int *begin, int *end)
{
    // assume end is one pass the last element. eg. arry + length;
    heapify(begin, end);

    while(begin != --end)
    {
        swap(*begin, *end);     // invariant: the next item to order will be at the top
        // after the swap, the next biggest/smallest item may not be
        // at the top. use push_down to fix this and preserve the heap property.
        push_down(begin, end);  
    }
}

Note that you do not call heapify inside the loop. After the swap, only the top element might violate the heap property -- the rest of the remaining elements are still in a heap. To fix the top you just need to push_down that element until it reaches the right level. This can be done in O(log n) since that's how deep the tree can ever be.

Edit: Added more explanation and example.

An analogy might help clear up the idea behind heapsort. You can think of heapsort as hosting an elimination tournament where in each match-up bracket 3 contenders duke it out. The winner will move up the bracket to the next match-up and the 2 losers stay where they are. The tournament starts out by doing all the match-ups at the bottom bracket first, progressively moving up -- this is basically the heapifying phrase.

After you heapify, that's finishing one entire tournament -- the champion is at array[0] and the runner-ups will be either array[1] or array[2]. To find the runner-up you host another match-up between them plus a 3rd contender from the bottom bracket.

Now if you think of 'push_down' as a sort of scorekeeper, his job is to keep track of the winners and move them up the bracket + what match-ups need to take place. Each match-up has 1 'defender'(the guy one bracket up) and 2 'challengers'. If the defender loses, he swaps places with the challenger that defeated him. If there are more challengers below the defender's new spot, another match-up is between them. The defender will get pushed further and further down the match-up bracket until he can successfully defend his spot or there are no more opponents to defend against.

The 'push_down' function is probably the most important helper since that's where the reordering actually happens. It's almost analogous to partition in qsort or merge in mergesort.

Here's basically what the push_down function would look like: (note, it's not thoroughly tested)

void push_down(int *begin, int *end, size_t defender = 0)
{
    // at the very bottom?
    if(defender >= std::distance(begin, end) / 2) return;

    size_t challenger = defender * 2 + 1;
    // is there a right-child?
    // Note that in even# arrays, last parent doesn't have a right child
    if(begin + challenger + 1 != end)   
        if(begin[challenger + 1] < begin[challenger])
            ++challenger;

    // defended successfully?
    if( !(begin[challenger] < begin[defender]) ) return;

    // challenger wins
    std::swap(begin[challenger], begin[defender]);
    push_down(begin, end, challenger);
}

Note that the array will be sorted in descending order if smallest is at the top. But this is trivial to fix once sorting is working -- just flip the comparison being done.

You should heed the advice from the other answers and extract out those functions. It will make your code easier to reason about.

Answer 2

int length=0,min_heapified=0,start_length=0,index=0;

I prefer one declaration per line because it's easier to read and find the type of variables. Furthermore, min_heapified is only used inside the do-while loop, so declare it there:

do {       
    int min_heapified = 0;
    do {
...

---

Change

if(x<=(length-1))

to

if (x < length)

It's more common and simple.

---

Instead of

int swap=array[left];
array[left]=array[root];
array[root]=swap;

you should create a swap function. Maybe it already exists in a library.

int swap(array, index, rootIndex) {
    int swap = array[index];
    array[index] = array[rootIndex];
    array[root] = swap;
}

---

If I'm right you could extract the following to a new function:

if(array[left]<array[root])
{
    int swap=array[left];
    array[left]=array[root];
    array[root]=swap;
    min_heapified=1;    
}

It looks for me that the other if do the same. The only difference is the used index, so I'd write something like this:

int swapIfLess(array, index, rootIndex) {
    if (array[index] < array[rootIndex]) {
        swap(array, index, rootIndex)
        return 1;   
    }
    return 0;
}

if (left < length) {
    if (swapIfLess(array, left, root)) {
        min_heapified=1;    
    }
}
if (right < length) {
    if (swapIfLess(array, right, root)) {
        min_heapified=1;    
    }
}

---

The i variable looks unnecessary:

int root=i;

Use the root variable in the for loop:

for (int root = 0; root < length; root++)

Maybe you should rename it to rootIndex.

---

Extract more functions. The for loop (inside the do-while loops) looks as a good candidate for this. Additionally, you should have a readInputArray function and a printResults function too.

Answer 3

Lets declare one variable per line.
Also don't declare all you variables at the top. Declare them as close to the use point as possible.

    int length=0,min_heapified=0,start_length=0,index=0;

Declaring arrays like this is not valid. It is C functionality. your compiler is letting you get away with it but not all compiler will. The size of the array must be static and known at compile time. If you need to dynamical size arrays then use std::vector

    int array[length],sorted_array[length];

C++ already has a std::swap() use that rather than doing it manually.

use < rather than <= (it looks more natural for most C/C++ programmers). In your case it is especially a god thing as you are subtracting one anyway.

if(root <= (length-1))
// Prefer the following
if(root < length)

This is an un-needed test:

if(root < length)

root is i and i is the loop variable constrained to be less then length. While we are here you should not use i as a variable name. It conveys no meaning (this is not fortran). Name your variables. Also think about the maintainer searching for all uses of i is a real pain as the letter i is used everywhere. Name your variables so it can be easily found.

Prefer to use pre-increment.

for(int root=0;root<length;root++)
// prefer
for(int root=0;root<length;++root)

In this case it makes no difference. But when using class types (like a lot of iterators) the standard way to implement post increment is to do a copy (as the return value) then call pre-increment. Thus it can be slightly less efficient to use post increment when loop variable is a class type. The problem with post increment comes not when you write the code but when you maintain it. If sombody converts the container to a standard container and then converts the loop to iteratos etc you need to spot and change the increment. By being consistent and always using pre-increment changes to the types have less affect on changes to the code (ie it help when types are changed (especially when the type change is a long way from the type being used).

You are using min_heapified as a boolean. Declare it as such and use appropriately.

min_heapified=0;

While you are at it. Declare it here and not at the top.

bool min_heapified = false;

Answer 4

This is an improved version of the previous code:

1. The max heapify logic was flawed, which is now fixed.
2. This one is modularized, more readable as a recursive function is used.

 #include <iostream.h>
 #include <stdlib.h>
 #include <time.h>
 #include <stdlib.h>
/*This code is written by NF at 241211,algorithm taken from cormens intro to algorithm,This algorithm has clear distinction in between the the max_heapify and build_max_heap function;The previous version had used only a naive approach of build_max_heap at each iteration and was explotingexploiting all the nodes of the heap tree,so it was very slow,having O(n^2)complexity,this code sorts 8483876 reversed elements within 4.4 secs(worst case) */

 int swap(int *a, int l, int r)
 {    
    int swap_variable=a[l];
    a[l]=a[r];
    a[r]=swap_variable;

  return 0;
 }

int left(int i)
{
  return (2*i)+1; 
}
int right(int i)
{
  return (2*i)+2; 
}

 int max_heapify(int *array,int i,int length)
 {    
  int l=left(i);
  int r=right(i);
  int largest=0;

 if((l<length) && (array[l]>array[i]))
 {
    largest=l;
 }
 else
 {
    largest=i;
 }
 if((r<length) && (array[r]>array[largest]))
 {
     largest=r;
 }

  if(largest!=i)
  {
    swap(array,i,largest);
    max_heapify(array,largest,length);   
  }
  return 0;        
}

int build_max_heap(int *a,int length)
{
   for(int i=(length/2);i>=0;i--)
   {
      max_heapify(a,i,length);
    }
    return 0;    
  }

 int heap_sort(int *a,int length)
 {    
    build_max_heap(a,length);

    for(int i=length-1;i>=1;i--)
    {
      swap(a,0,i);
      length--;
      max_heapify(a,0,length);    
   }
}


int main()
{
  int length = 0;
  cout<<"Enter Array Length:";
  cin>>length;

  int array[length];
int count=0;

  for(int i=0;i<length;i++)
  {
     array[i]=rand()%100;
  }
  cout<<"Array filled with random elements..sorting started...:"<<endl;
  //cout<<"Before sort:"<<endl;
  //for(int i=0;i<length;i++)cout<<array[i]<<" ";

  clock_t start = clock();
  heap_sort(array, length);
  cout<<"Sorting done!..Time elapsed:"<<((double)clock()-start)/CLOCKS_PER_SEC; 

  //for(int i=0;i<length;i++)cout<<array[i]<<" ";                        
}