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.
Programming Praxis 
[…] 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):
import qualified Data.Vector as V (!) :: V.Vector a -> Int -> a v ! i = v V.! (i-1) swap :: Int -> Int -> V.Vector a -> V.Vector a swap i j heap = heap V.// [(i-1, heap ! j), (j-1, heap ! i)] siftup :: Ord a => Int -> V.Vector a -> V.Vector a siftup i heap = let j = div i 2 in if i == 1 || heap ! j <= heap ! i then heap else siftup j $ swap i j heap siftdown :: Ord a => Int -> V.Vector a -> V.Vector a siftdown n = f 1 where f i heap = if 2*i > n || heap ! i <= c then heap else f j $ swap i j heap where (c, j) = minimum [(heap ! x, x) | x <- [2*i, 2*i+1], x <= n] hsort :: Ord a => V.Vector a -> V.Vector a hsort heap = foldr (\i -> siftdown (i - 1) . swap 1 i) (foldl (flip siftup) heap [2..V.length heap]) [2..V.length heap]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.
class ArrayHeap def initialize(seq = nil, &block) @ord = block @heap = [nil] # Cheap way of getting 1-based indexing seq.each {|item| push(item)} unless seq.nil? end def length @heap.length - 1 end def empty? length == 0 end def top return nil if empty? @heap[1] end def pop return nil if empty? # Swap root with element at end @heap[1], @heap[-1] = @heap[-1], @heap[1] min = @heap.pop siftdown return min end def push(item) @heap.push(item) siftup end def inspect "<ArrayHeap " + @heap[1..-1].inspect + ">" end private # Move top of heap down to maintain heap invariant def siftdown i = 1 while 2*i <= length do j = 2*i if j+1 <= length and @ord.call(@heap[j+1], @heap[j]) then j += 1 end break if @ord.call(@heap[i], @heap[j]) @heap[i], @heap[j] = @heap[j], @heap[i] i = j end end # Move bottom of heap up to maintain heap invariant def siftup i = length while i > 1 do break if @ord.call(@heap[i/2], @heap[i]) @heap[i], @heap[i/2] = @heap[i/2], @heap[i] i /= 2 end end end def heapsort(list) h = ArrayHeap.new(list) {|a,b| a<b} r = [] while (item = h.pop) do r << item end return r end irb(main):015:0> heapsort [9,1,4,27,33,21] => [1, 4, 9, 21, 27, 33]# A Python version class Heap: ''' Simple heap impl, with 'min' at the top ''' def __init__(self): self.arr = [None] self.n = 0 def siftup(self, ele): parent = ele / 2 if parent > 0 and self.arr[ele] < self.arr[parent]: self.arr[parent], self.arr[ele] = self.arr[ele], self.arr[parent] self.siftup(parent) def siftdown(self, ele): left = ele * 2 right = ele * 2 + 1 smaller = None arr = self.arr # case where l & r both exist if left <= self.n and right <= self.n: if arr[left] < arr[right]: smaller = left else: smaller = right elif left <= self.n: smaller = left elif right <= self.n: smaller = right if smaller is not None and arr[ele] > arr[smaller]: arr[ele], arr[smaller] = arr[smaller], arr[ele] self.siftdown(smaller) def insert(self, ele): self.n = self.n + 1 self.arr.append(ele) self.siftup(self.n) def get_min(self): tmp = self.arr[1] self.arr[1] = self.arr[self.n] self.n = self.n - 1 self.siftdown(1) return tmp def is_empty(self): return self.n < 1 def heap_sort(lst): heap = Heap() for ele in lst: heap.insert(ele) while not heap.is_empty(): yield heap.get_min() print (list(heap_sort([14, 4, 5, 16, 6, 1, 19, 2, 99, 3, 10, 8, 21])))[…] Imperative Heaps (programmingpraxis.com) […]