## Heap Sort

### November 6, 2009

We begin with a simple version that implements the heapsort algorithm directly:

`function swap(A,i,j, t) {`

t = A[i]; A[i] = A[j]; A[j] = t }

`function heapify(A,left,right, p,c) {`

for (p=left; (c=2*p) <= right; p=c) {

if (c<right && A[c] < A[c+1]) c++

if (A[p] < A[c]) swap(A, c, p) } }

`function sort(A,n, i) {`

for (i=int(n/2); i>=1; i--)

heapify(A, i, n)

for (i=n; i>1; i--) {

swap(A, 1, i)

heapify(A, 1, i-1) } }

By moving the swap inline, we can move the invariant part of the swap out of the inner loop:

`function heapify(A,left,right, p,c,t) {`

t = A[left]

for (p=left; (c=2*p) <= right; p=c) {

if (c<right && A[c] < A[c+1]) c++

if (t < A[c]) A[p] = A[c]; else break }

A[p] = t }

`function sort(A,n, i,t) {`

for (i=int(n/2); i>=1; i--)

heapify(A, i, n)

for (i=n; i>1; i--) {

t = A[1]; A[1] = A[i]; A[i] = t

heapify(A, 1, i-1) } }

It has been shown empirically that instead of heapifying from the top it is better to sift the item at the top of the heap all the way to the bottom, then sift it back up to its proper position, eliminating the comparison between a parent and its smallest child on the trip down:

`function heapify(A,left,right, p,c,t) {`

t = A[left]

for (p=left; (c=2*p) <= right; p=c) {

if (c<right && A[c] < A[c+1]) c++

A[p] = A[c] }

for (c=p; (p=int(c/2)) >= left; c=p) {

if (t > A[p]) A[c] = A[p]; else break }

A[c] = t }

`function sort(A,n, i,t) {`

for (i=int(n/2); i>=1; i--)

heapify(A, i, n)

for (i=n; i>1; i--) {

t = A[1]; A[1] = A[i]; A[i] = t

heapify(A, 1, i-1) } }

Our final version moves the heapify function inline:

`function sort(A,n, l,r,p,c,t) {`

if (n > 1) {

l = int(n/2) + 1; r = n

while(1) {

if (l > 1) t = A[--l]

else { t = A[r]; A[r--] = A[1]

if (r == 1) { A[1] = t; return } }

for (p=l; (c=2*p) <= r; p=c) {

if (c < r && A[c] < A[c+1]) c++

A[p] = A[c] }

for (c=p; (p=int(c/2)) >= l; c=p) {

if (A[p] < t) A[c] = A[p]; else break }

A[c] = t } } }

Like quicksort, heapsort runs in time *O*(*n* log *n*). The final heapsort is quite fast, nearly as fast as a well-tuned quicksort and without the annoying possibility of a quadratic worst-case. The code, including the test suite from the prior exercise, is collected at http://programmingpraxis.codepad.org/6HryLp9f, but you can’t run it, because codepad doesn’t provide an Awk interpreter.

here is my implementation in c