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 xi is greater than x2i and x2i+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 x1..n−1 is unlikely to remain a heap if a new item is placed at xn. The siftup function restores the heap property to x1..n by repeatedly swapping the item at xn with its parent at xn/2 until it reaches its proper place in the heap.

The siftdown operation takes a heap stored in a sub-array x1..n in which the item at x1 is out of place and restores the heap property to x1..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 x1..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.

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: