## Imperative Heaps

### January 25, 2013

We’ll write our program in Awk instead of Scheme; Scheme has the ability to manipulate arrays and write do-loops, but to my functional eyes, such code just looks … wierd. We start with the swap function that is used in both siftup and siftdown:

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

t = x[i]

x[i] = x[j]

x[j] = t }

The siftup function stores the current node at *i* and calculates the parent node at *p*. The `while`

loop stops when the *i* node reaches either the root of the heap or its proper position within the heap:

`function siftup(n, i, p) {`

i = n

while(1) {

if (i == 1) break

p = int(i / 2)

if (x[p] <= x[i]) break

swap(p, i)

i = p } }

The siftdown function is similar to siftup, but calculates a child node instead of a parent node, and also compares the two siblings:

`function siftdown(n, i, c) {`

i = 1

while(1) {

c = 2 * i

if (c > n) break

if (c+1 <= n)

if (x[c+1] < x[c])

c++

if (x[i] <= x[c]) break

swap(c, i)

i = c } }

Sorting first forms a heap, then extracts the items from the heap in order, reversing the items in the process of extracting them:

`function hsort(n, i) {`

for (i = 2; i <= n; i++)

siftup(i)

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

swap(1, i)

siftdown(i-1) } }

We test by building an array and sorting it:

`BEGIN {`

split("4,7,8,1,5,3,2,9,6", x, ",")

hsort(9)

for (i = 1; i <= 9; i++)

print x[i] }

Output is the numbers 9, 8, 7, 6, 5, 4, 3, 2, 1; to return the numbers in ascending order, reverse the sense of the comparisons. You can see the program at http://programmingpraxis.codepad.org/GNupGt4H.

[…] today’s Programming Praxis exercise, our goal is to implement an array-based heap. Let’s get started, […]

My Haskell solution (see http://bonsaicode.wordpress.com/2013/01/25/programming-praxis-imperative-heaps/ for a version with comments):

Went ahead and did this for the previous exercise: Splay heaps redux–imperative model

Personally, I think this one makes more sense (even in a functional language), but to each their own.

[…] Pages: 1 2 […]

The imperative sort is ideal for languages like Ruby and Python which prefer variable sized arrays over linked structures. I wrote this as a Heap class in Ruby, so the heapsort is just a perfunctory testing function, not an in-place sort.

[…] Imperative Heaps (programmingpraxis.com) […]