Algorithms in a Nutshell

(^88) | Chapter 4: Sorting Algorithms
(and so on) to properly maintain the Heap property forA. As you can see, large
numbers are eventually “lifted up” in the resulting heap (which means they are
swapped inAwith smaller elements to the left). The grayed squares in Figure 4-16
depict the elements swapped in line 9 ofheapify.
HEAPSORTsorts an arrayAof sizenby treating it as two distinct subarrays,
A[0,m) andA[m,n), which represent a heap of sizemand a sorted subarray of
n–melements, respectively. Asiiterates fromn–1 down to 1, HEAPSORTgrows
the sorted subarrayA[i,n) downward by swapping the largest element in the heap
(at positionA[0]) withA[i] (line 3 ofsortin Figure 4-14); it then reconstructs
A[0,i) to be a valid heap by executingheapify(whose pseudocode is shown in
Figure 4-14). The resulting non-empty subarrayA[i,n) will be sorted because the
largest element in the heap represented inA[0,i) is guaranteed to be smaller than
any element in the sorted subarray A[i,n).
Context
HEAPSORT is not a stable sort. Because it moves elements around quite
frequently, it should not be used for value-based data.
Forces
HEAPSORTavoids many of the nasty (almost embarrassing!) cases that cause
QUICKSORTto perform badly. Nonetheless, in the average case QUICKSORT
outperforms HEAPSORT.
Solution
A sample implementation in C is shown in Example 4-9.
Figure 4-15. (a) Sample heap of 16 unique elements; (b) labels of these elements; (c) heap
stored in an array
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use