Algorithms in a Nutshell

Heap Sort | 87

Sorting

Algorithms

heap in an array by storing the element value for a node in the array position iden-

tified by the node’s label. The array shown in illustration (c) in Figure 4-15

represents the heap shown in that figure. The order of the elements withinAcan

be simply read from left to right as deeper levels of the tree are explored.

HEAPSORTsorts an array by first converting that array “in place” into a heap.

Indeed, the heap shown in Figure 4-15 results by executingbuildHeap(whose

pseudocode is shown in Figure 4-14) on an already sorted array. The progress of

buildHeapis shown in Figure 4-16. Each numbered row in this figure shows the result

of executingheapifyon the initial array from the midway point of⎣n/2⎦–1 down to

the leftmost index 0.heapify(A,i,n) updatesAto ensure that elementA[i]is

swapped with the larger of its two children,A[2*i+1] andA[2*i+2], should either one

be larger than A[i]. If the swap occurs,heapifyrecursively checks thegrandchildren

Figure 4-14. Heap Sort fact sheet

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