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
+ 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 #include 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
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 #include You don't need any of these headers for any of the code you posted. Also, use instead of . 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 . 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.