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.

About these ads

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, […]

  2. 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]
    
  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. 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[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]
    
  5. 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[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])))
    
  6. […] Imperative Heaps (programmingpraxis.com) […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 634 other followers

%d bloggers like this: