Definitions
from Wiktionary, Creative Commons Attribution/ShareAlike License
 n. A sorting algorithm based on the heap data structure.
 v. (computing) To sort with such an algorithm.
Etymologies
from Wiktionary, Creative Commons Attribution/ShareAlike License
Examples

8.4 Heapsort In this section we develop a sorting algorithm called heapsort whose worst case as well as average case running time is O (nlogn).

There are other methods, such as heapsort and mergesort, that take O (nlogn) time in the worst case, although their average case behavior may not be quite as good as that of quicksort.

You can test it with: java. exe com. mindprod.heapsort.

It doesn't matter if the element space is limited: heapsort is still

It doesn't matter if the element space is limited: heapsort is still O (n log n), merge sort is still O (n log n).

Thus, heapsort, modified to produce only the first k elements takes O (n + k log n) time.

Sort them using (a) quicksort, (b) insertion sort, (c) heapsort, and (d) bin sort, treating them as pairs of digits in the range 09.

First, here's a taster  a static visualisation of heapsort:

In the diagram the "rabbits" are the dark lines sweeping down to their positions rapidly, and the turtles are the lighter lines that gradually curve towards the top right of the image. heapsort image at the top of this article.

Data Structures and Algorithms: CHAPTER 8: Sorting i: integer; {cursor into A} begin {establish the partially ordered tree property initially} (1) for i: = n div 2 downto 1 do (2) pushdown (i, n); (3) for i: = n downto 2 do begin (4) swap (A [1], A [i]); {remove minimum from front of heap} (5) pushdown (1, i  1) {reestablish partially ordered tree property} end end; {heapsort} Fig. 8.18.
Comments
Log in or sign up to get involved in the conversation. It's quick and easy.