Algorithms in a Nutshell

Heap Sort | 89

Sorting

Algorithms

Figure 4-16. buildHeap operating on an initially sorted array

Example 4-9. Heap Sort implementation in C

static void heapify (void **ar, int(*cmp)(const void *,const void *),

int idx, int max) {

int left = 2*idx + 1;

int right = 2*idx + 2;

int largest;

/* Find largest element of A[idx], A[left], and A[right]. *

if (left < max && cmp (ar[left], ar[idx]) > 0) {

largest = left;

} else {

largest = idx;

}

if (right < max && cmp(ar[right], ar[largest]) > 0) {

largest = right;

}

/* If largest is not already the parent then swap and propagate. */

if (largest != idx) {

void *tmp;

tmp = ar[idx];

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