PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: High Entry average rating: No information on entry rating
heapsort (Algorithm)

The heapsort algorithm is an elegant application of the heap data structure to the sorting problem. It consists of building a heap out of some list of $ n$ elements, and the removing a maximal value one at a time.

The Algorithm

The following pseudocode illustrates the heapsort algorithm. It builds upon the heap insertion and heap removal algorithms.

Algorithm HEAPSORT( $ (A,\preceq,n)$)
Input: List $ A$ of $ n$ elements
Output: $ A$ sorted, such that $ \preceq$ is a total order over $ A$

begin
$\textstyle \parbox{\textwidth}{ \textbf{for} $i\gets2\bf{ to }n$\ \textbf{do}\\... ... \hspace*{0.4in}\parbox{\textwidth}{$A[i-1]\gets\bf{HeapRemove}(H,i,\preceq)$}}$
end

Analysis

Note that the algorithm given is based on a top-down heap insertion algorithm. It is possible to get better results through bottom-up heap construction.

Each step of each of the two for loops in this algorithm has a runtime complexity of $ \mathcal{O}(\log i)$. Thus overall the heapsort algorithm is $ \mathcal{O}(n\log n)$.

Heapsort is not quite as fast as quicksort in general, but it is not much slower, either. Also, like quicksort, heapsort is an in-place sorting algorithm, but not a stable sorting algorithm. Unlike quicksort, its performance is guaranteed, so despite the ordering of its input its worst-case complexity is $ \mathcal{O}(n\log n)$. Given its simple implementation and reasonable performance, heapsort is ideal for quickly implementing a decent sorting algorithm.



"heapsort" is owned by mathcam. [ full author list (3) | owner history (2) ]
(view preamble)

View style:

See Also: heap insertion algorithm, heap removal algorithm, heap, sorting problem

Log in to rate this entry.
(view current ratings)

Cross-references: ordering, stable sorting algorithm, in-place sorting algorithm, quicksort, heap, heap insertion algorithm, algorithm
There are 5 references to this entry.

This is version 6 of heapsort, born on 2002-03-07, modified 2004-04-02.
Object id is 2755, canonical name is Heapsort.
Accessed 16086 times total.

Classification:
AMS MSC68P10 (Computer science :: Theory of data :: Searching and sorting)

Pending Errata and Addenda
None.
[ View all 3 ]
Discussion
Style: Expand: Order:
forum policy
See balanced binary tree by rmilson on 2002-03-24 23:37:11
Initially this entry confused me. I kept
wondering, "Where are the parent/child links?"

I didn't quite grok this till I remembered that a
heap is a balanced binary tree, and as such can
be represented by an array. So entry 0 is the
parent of entries 1,2 which in turn are the parents
of entries 3,4 and 5,6 respectively, etc.

The problem, I guess, is that "balanced binary tree"
is two clicks away from "heapsort", and I missed
this vital bit of information on the first pass
over the material
[ reply | up ]

Interact
post | correct | update request | add example | add (any)