By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
445,813 Members | 1,252 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 445,813 IT Pros & Developers. It's quick & easy.

Problem with Heap Sort

P: n/a
The following code is for heap sort but its not working properly.
According to my analysis the Logic is correct but still its not showing
the correct output.
Thanks.

#include "stdafx.h"
#include<iostream>
#include<stdlib.h>

using namespace std;

int n=10,s[10]={11,2,9,13,57,25,17,1,90,3},heapsize;

void swap(int a,int b)
{
int temp=s[b];
s[b]=s[a];
s[a]=temp;
}

void keepheap(int i)
{
int l,r,p,q,t,largest,m;

l = 2*i;
r = 2*i + 1;

p = s[l];
q = s[r];
t = s[i];

if(l<=heapsize && p > t)
largest = l;
else
largest = i;

m = s[largest];

if(r<=heapsize && q > m)
largest = r;

if(largest != i)
{
swap(i, largest);
keepheap(largest);
}
}
void makeheap(int n)
{
heapsize=n;
for(int i=(n/2)-1; i>=1; i--)
keepheap(i);
}

void heapsort()
{
makeheap(n);

for(int i=n; i>=2; i--)
{
swap(1,i);
heapsize--;
keepheap(i);
}
}

Jun 1 '06 #1
Share this Question
Share on Google+
1 Reply


P: n/a
co******@gmail.com wrote:
The following code is for heap sort but its not working properly.
According to my analysis the Logic is correct but still its not showing
the correct output.
Thanks.
A general observation before I go into specific errors. Arrays in C++
start at index 0, not at index 1. That is, if you define an array:
int s[10];

the values you may access are s[0] through s[9]. Specificalloy, s[10]
is NOT a valid value.

#include "stdafx.h"
#include<iostream>
#include<stdlib.h> You don't need any of these headers for any of the code you posted.
Also, use <cstdlib> instead of <stdlib.h>. stdlib.h has been deprecated
for at least 8 years.

using namespace std;

int n=10,s[10]={11,2,9,13,57,25,17,1,90,3},heapsize;
Avoid global variables (not an error, just a guideline).

void swap(int a,int b)
{
int temp=s[b];
s[b]=s[a];
s[a]=temp;
} There is nothing wrong with your swap function, but in general try to
use std::swap, declared in <algorithm>.

void keepheap(int i)
{
int l,r,p,q,t,largest,m;
First problem, you should check to make sure i is valid before
continuing. Something like:
if (i >= heapsize)
return;

l = 2*i;
r = 2*i + 1; If you use a zero based array to represent a tree, the left subchild
will be at 2*i+1, and the right at 2*i+2. So change this to:
l = 2*i+1;
r = 2*i+2;

p = s[l];
q = s[r];
t = s[i];
What if l or r are outside of the valid range? You don't check for that
until later. I suggest dropping these variables completely, as they
just serve to muddy up your algorithm.

if(l<=heapsize && p > t)
largest = l;
else
largest = i;

Again. s[heapsize] is NOT valid. So you should be checking for (l <
heapsize). Also, having removed p,q, and t, the second clause should be
(s[l] > s[i]). Putting it all together:

if (l < heapsize && s[l] > s[i])
largest = l;
else
largest = i;

This is probably a case where I'd use the ternary operator, and collapse
this whole thing to:

largest = (l < heapsize && s[l] > s[i]) > l : i;

If that confuses you, ignore it, as the if statement will do just as well.
m = s[largest]; Again, drop this variable. It just makes the algorithm harder to follow.

if(r<=heapsize && q > m)
largest = r;
This suffers from the same problem. You should be checking for (r <
heapsize && s[r] > s[largest]). You could also use the ternary operator
here if it looks cleaner to you.

if(largest != i)
{
swap(i, largest);
keepheap(largest);
}
}
void makeheap(int n)
{
heapsize=n;
for(int i=(n/2)-1; i>=1; i--)
keepheap(i);
}
Same issue. Arrays are zero based. You should loop while (i >= 0).

void heapsort()
{
makeheap(n);

for(int i=n; i>=2; i--) Arrays are zero based. As your intent here was to skip the last
iteration of the loop (which is fine) you should loop while (i >= 1).
Likewise, s[n] is NOT valid. You should start with i=n-1.
{
swap(1,i);
Arrays are zero based (last time, I promise). You want to swap(0, i). heapsize--;
keepheap(i);
Here you are trying to maintain the heap property on the element you
just removed from the heap, which doesn't make any sense. The element
for which you (possibly) destroyed the heap property is the root, so
keepheap(0).
}
}


Good luck.

--
Alan Johnson
Jun 1 '06 #2

This discussion thread is closed

Replies have been disabled for this discussion.