## 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.

Pages: 1 2

### 7 Responses to “Imperative Heaps”

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

```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]
```
3. jpverkamp said

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.

4. […] Pages: 1 2 […]

5. David said

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
end

def pop
return nil if empty?

# Swap root with element at end
@heap, @heap[-1] = @heap[-1], @heap
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]
```
6. Joe A said
```# 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
self.arr = 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])))
```
7. […] Imperative Heaps (programmingpraxis.com) […]