Talk:Heapsort
From Wikipedia, the free encyclopedia
Contents |
[edit] C-code
The example C-code was tested and found to be flawed. The following test vector {2,5,3,4,1} returned {1,2,4,3,5}. Many other failing examples have been found. The problem seems to be in the build heap portion of the code, which sometimes fails to create a valid max-heap. When the sift_in function is replaced with a simpler sift_down function for building the heap, the code works.
Also, the comments of the sift_in function seem incorrect. The function first performs a sift_down and then a sift_up, unless you are viewing the heap upside down.
—The preceding unsigned comment was added by Rekinser (talk • contribs) 21:41, 8 December 2006 (UTC).
I concur. The initial heap build does not work. The build phase examines the first half of the data, in reverse order. With other algorithms, this only affects children that are to the right of the entry being processed. Hence the max heap property is progressively made true with right to left processing of all non-leaf entries.
Where the C code fails is that its "sift_in" will affect parent nodes of the initial "free" node being processed.
A bit of horrible patching on "sift_in" does make it work:
a) Change its parameter from "free" to be "free_in"
b) Add "unsigned free = free_in;" at the start
c) Modify the "while"'s "(i=free/2)" to say "((i=free/2)>=free_in)"
MESSY! Probably not optimal. Can anyone suggest a more sensible change? Lauwr 00:06, 23 January 2007 (UTC)
The C code does not include stdlib and I realize that "free" is a descriptive variable name, but wouldn't it still be good practice not to have a variable name that could so easily be confused with the stdlib function? 85.11.196.122 07:32, 23 January 2007 (UTC)
[edit] Numerical Recipies copyright
Is it acceptable to use code adapted from Numerical Recipies in C? I don't own a copy, so I can't quote it, but I am led to understand that it is very restrictive in its usage licence. — PhilHibbs | talk
- That's correct. The code can only be used on one screen if you purchase a single-screen license; distribution is prohibited. Deco 00:27, 27 Apr 2005 (UTC)
[edit] Pseudocode question
I'm fairly certain that the pseudocode in this article does not work on some arrays of odd length. That is, if length(a) is odd, then occassionally heapSort(a) produces an array that is one swap away from sorted. For example,
heapSort([1,2,3]) -> [1,3,2]
and
heapSort([2,1,3,5,4]) -> [1,2,4,3,5].
If, in heapSort, I replace the line
var int start := count / 2 - 1
with
var int start := count / 2
it seems to correct the bug. Have I missed something? --Quaternion 22:28, 18 Feb 2005 (UTC)
- The pseudocode works for me. Make sure you are really using integer based variables for the value of start, or take the floor value of count/2. For example, in perl I said
my $start = int($count / 2) - 1;--Dustball 02:36, 4 July 2006 (UTC)
Is it for some reason impractical to implement a quaternary heapsort?
- It's not impractical to implement a quaternary heapsort. In fact, I managed to implement an N-ary Heapsort algorithm in Java. — pguedes
i think there's a bug in the final line of the python program. should it not be called with the first element of the array, 1 instead of with 0?
To my mind O(N log N) is not approximately linear for large N, but I suppose it depends on your viewpoint. There are sort methods which are linear - e.g pigeon hole sort for a densely populated set of integers, and these could be expected to run significantly faster.
However, both heapsort and quicksort are, for most practical purposes, amongst the fastest sorts. Note that scrambling the elements before doing a quicksort is often more effective - as often the elements are almost in order, in which case quicksort is known to be slow. This does not apply to heapsort.
- I agree with the O(N log N) statement, and eliminated the claim that it's about linear. Scrambling the elements isn't a really effective strategy for improving quicksort, since scrambling involves a lot of cache misses, making it a very slow operation. Deco 19:36, 4 Nov 2004 (UTC)
The article states that an in-place (O(1) auxiliary space) quicksort is possible. Is that true? Don't you need a stack to manage what parts of the array you still need to sort? --Ryan Stone 15:52, 4 Nov 2004 (UTC)
- Oh, I see it now. The data stored on the stack in quicksort is the pivot positions. It is quite possible to compute, rather than store, the pivot positions, in restricted implementations — for example, in a quicksort implementation which always uses the median. I'm not aware of any fast in-place quicksort variant though. Deco 19:31, 4 Nov 2004 (UTC)
There is something I've always wondered about heapsort. When you've created the heap and starts to extract the largest element of it, you swap it with the element with the largest index in the heap to get the value in the right position (ie when you just have created the heap, the first thing you do is to swap the 1st element with the Nth, then heapify, then you swap the 1st element with the (N-1)th and heapify and so on). But if you do that you will most of a time get a very low value at the top of the heap (since the value was previously at the bottom of the heap), and since that value is pretty low the siftup will take longer. Why don't you instead implement the heap as a min-heap instead of a max-heap? Then the head would be at the right position directly (no need to swap) and you could make one of it's children (the element just after it) the head and then heapify. The heapifying would take shorter time on average wouldn't it? I mean, it obvoiusly wouldn't be asymptotically faster, but it would be faster, n'est pas? Gkhan 01:21, Feb 14, 2005 (UTC)
- And oh yeah, I realize that the talk-page isn't really the right forum for asking techincal questions, but indulge me Gkhan 01:22, Feb 14, 2005 (UTC)
-
- Note: I removed my previous answer here -- I had the algorithm Gkhan was describing completely wrong
- Put briefly, the algorithm you describe isn't very effective at all -- assymptotically it's worse than Bubble sort. Actually, what you describe is an expensive version of Selection sort.
- Here's the reason why it's so poor: The heapifying operation takes O(n log n). What you're suggesting is that we heapify n elements, then n - 1 elements, ... until finally heapifying an array with 1 element(ok, we could skip that, but it doesn't make too much of a difference, and does make the calculations below easier.
- The number of operations we do will thus be O(n log n) + O ( (n - 1) log (n - 1) ) + ... + O ( 1 log 1)
- So it's O ( sum(i = 1 to n) of i log i). I'm not if that can be simplified, but I do know that sum(i = 1 to n) of i is n(n + 1)/2. So your algorithm will be worse than O (n ^ 2).
- I don't think that on average, things will be much faster. Let me think about it and see if I can come up with an answer for that.--Ryan Stone 21:03, 18 Feb 2005 (UTC)
-
- Well, I've thought about this a bit more, and what I realized was that even if Gkhan's algorithm was faster in the average case, it still probably couldn't beat quicksort. Heapsort's greatest advantages over quicksort is its guaranteed O (n log n) and that it's an in-place sort. If you're willing accept poor performance on certain inputs anyway, you might as well go with quicksort.--Ryan Stone 02:08, 23 Feb 2005 (UTC)
[edit] pseudocode question #2
When getting the child, is multiplying root * 2 enough? I mean, root = 0, then child = 0? I'm thinking it should be ((root + 1) * 2) - 1
- For the sake of simplicity, the arrays are one-based. However, this should have been explicitly noted and now is. Thanks. Deco 02:01, 26 Jun 2005 (UTC)
- Oops, I was wrong here. It seems like other parts rely on it being zero-based. Hmm. Deco 28 June 2005 21:17 (UTC)
The comment that Heapsort is usually faster than Mergesort may be a bit dated.
On architectures with a (relatively) small CPU cache and large main memory (e.g. Pentiums), Heapsort is usually *much* slower than Mergesort, when the size of the array being sorted is significantly larger than that of the cache but less than half that of main memory, *because* there are so many cache misses (the penalty is appalling: on my home PC a Heapsort of, say, 500,000 32-bit integers takes about twice as long, and of 90,000,000, takes about 10 times as long, as Mergesort and Quicksort).
Heapsort should *not* be used for large N.
Re: the "sorting revisited" link: it just ain't so. By a stroke of luck, the v8 Intel C++ compiler optimizes binary Heapsort better than it optimizes Quicksort or Mergesort (if mergesort is coded in assembler to avoid branch mis-predictions it is slightly faster) (but I'll be damned if I can dream up an efficient way to do the same thing for Quicksort!). The analysis doesn't extend to *large* values of N, which is where Heapsort does very badly indeed. The Insertion Sort implementation used for the test cases is... non-standard and very inefficient... which knobbles both Quicksort and Mergesort. I recommend: *Pull* the link.
-James Barbetti
- This is interesting. I wasn't aware that heapsort had such terrible cache behaviour, but it makes sense considering its access pattern. I can add something regarding this. Deco 19:55, 11 July 2005 (UTC)
[edit] Pseudocode question #3
How does the following line of code translate to other languages?
var int root = start, child
How can two variables be assigned to a single varaiable? Can someone please explain how this works and perhaps split this line up into something that can carry over more easily into other languages?
Thank you -- Random Heapsort Investigator
- Presumably, it's like C, where int x, y; declares both x and y as integers. One can make an assignment as well, so int x = 2, y; declares both x and y as integers and sets x to be 2. Dysprosia 03:36, 15 August 2006 (UTC)
[edit] Quicksort not in-place
Isn't it inappropriate to state that an advantage of Heapsort over QuickSort is that Heapsort is in-place? After all, QuickSort seems to be easily done in-place as shown in the Quicksort article.
Quote:
Although somewhat slower in practice on most machines than a good implementation of quicksort, it has the advantages of worst-case O(n log n) runtime and being an in-place algorithm.
- Quicksort is not in place, as the article discusses at some length. Quicksort often uses an in-place partition, and has a space-saving tail-recursive variant, but even then it requires Ω(log n) space. The quote you gave is actually talking about heapsort, so it's an argument against your claim rather than for. Deco 00:30, 6 December 2005 (UTC)
[edit] is smoothsort the same as heapsort?
It seems smoothsort redirects to heapsort. Does this make sense? The table on sorting algorithm lists both heapsort and smoothsort as seperate. --Apantomimehorse 21:21, 20 August 2006 (UTC)
I noticed the same thing. Have a look under "Variations" and they do talk about smoothsort though.
http://en.wikipedia.org/wiki/Smoothsort#Variations
Blakeops 06:40, 2 February 2007 (UTC)
[edit] correcting a heapsort reference
chuck bradley, bradley@tiac.net the reference to introduction to algorithms is partly wrong. chpt 6 is called heapsort. it covers heaps, heapsort, and priority queues. chapter 7 is quicksort.
[edit] Two versions of the code?
The second version of the pseudocode gives a feeling of dissonance to this article. I think it's because of the way the intro to the second version complains slightly about the example before it. Can something be done to correct this? --Masamage 17:14, 7 December 2006 (UTC)
[edit] Pseudocode changes and clarifications
The strange thing about the above implementation is that it uses heapify-down operations to achieve what we really want to achieve using heapify-up operations. Imagine building the heap. As we add new elements, we want them to crawl up the heap. For the actual sorting, however, the standard implementation jibes with intuition. The following implementation jibes completely with intuition and is still O(n log n).
The two implementations are equivalent, except in the order in which they process data. The first one starts at the bottom and moves up while sifting down, while the second starts at the top and moves down while sifting up. Either way is acceptable and neither is strange to me. The only plus side to using the first piece of code is that you only need one sift function, other than that they are equivalent in execution time.
I am having trouble understanding some of the notation used in this function.
function siftup(a, start) {
var int child := start, root, remainder
while child > 0 {
remainder := (child - 1) % 2
root := ((child - 1) - remainder) / 2
if a[root] < a[child]
swap(a[root], a[child])
child := root
else
return
}
}
So I rewrote it. Most languages default to integer division operations when using integers. So unless start, child, and/or root are defined as floating point they are unlikly to cause floating point division in the Java, or C languages. This algorithm is correct, but the remainder is (in this algorithm) equivalent to using the floor function.
I changed the original sift down function to take the end as a parameter instead of count, because it may be difficult to understand that sift(a, 0, end) means to sift down all the way except for the last element in the heap as you are inputting end for count. I also changed the format to be in greater accordence with Wikipedia:Algorithms_on_Wikipedia. --ANONYMOUS COWARD0xC0DE 08:10, 18 December 2006 (UTC)
[edit] Wikibook Quotation
Why not to use implementation suggested in Wikibook Algorithm implementation? KorDen 16:27, 20 February 2007 (UTC)
