## Imperative Heaps

### January 25, 2013

When I made the list of heap algorithms in the previous exercise, I realized that we don’t have an implementation of what is probably the most common form of heaps, the mutable heaps of imperative languages implemented in an array *x*. The basic idea is to arrange the items in the array so the largest is at index 1, and each item *x _{i}* is greater than

*x*

_{2i}and

*x*

_{2i+1}(that’s a max-heap—a min-heap with the smallest item at the root has the sense of the comparison reversed).

A heap stored sub-array *x*_{1..n−1} is unlikely to remain a heap if a new item is placed at *x _{n}*. The

*siftup*function restores the heap property to

*x*

_{1..n}by repeatedly swapping the item at

*x*with its parent at

_{n}*x*

_{n/2}until it reaches its proper place in the heap.

The *siftdown* operation takes a heap stored in a sub-array *x*_{1..n} in which the item at *x*_{1} is out of place and restores the heap property to *x*_{1..n} by repeatedly swapping the out-of-order item with its lesser child until it reaches the proper place in the array.

Given the siftup and siftdown operations, sorting an array is easy. First, for each item from the second to the last, sift it up to its proper position, forming a heap in *x*_{1..n}. Then, swap each item from the last to the second with the first item and sift the new first item down to its proper position in the heap.

Your task is to write functions that implement the siftup, siftdown, and heapsort procedures. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

[...] 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) [...]