Heaps

I noted in my last post that I had a technical phone interview. When it was scheduled, the HR person told me that it would include "data structures, algorithms, and architecture". I decided that it wouldn't be a bad idea to review a bit and so I got a copy of Steven Skiena's "The Algorithm Design Manual" and started rummaging through it.

One of the data structures that I came across was a heap (as in heapsort if you've forgotten). A heap is a binary tree data structure that has the property that the parent is smaller for a min-heap or larger for a max-heap than its children. They can be used for priority queues as the minimum or maximum is always at the top of the heap or for sorting assuming that you a) take the top element and then b) recalculate the tree.

The code here follows Skiena's pretty closely excepting he starts his array at 1 and I use the more natural (for me anyway) 0 start. This code also implements only a min-heap, but you should take a bit of time to see if you can figure out how to make it either a min-heap or a max-heap as an initialization parameter. A couple of other things aren't that pretty (extract_min! in particular bugs me), but mostly it's not bad and is straight forward.

So ... here's the code

class Heap
    def initialize(a)
        @q = []
        a.each { |v| insert(v) } if a
    end

    def parent(n)
        n == 0 ? -1 : (n-1) / 2
    end

    def young_child(n)
        (2 * n) + 1
    end

    def insert(v)
        @q << v
        bubble_up(@q.size-1)
    end

    def bubble_up(n)
        return if parent(n) == -1 # Root of heap, no parent 
        if @q[parent(n)] > @q[n]
            swap(n, parent(n))
            bubble_up(parent(n))
        end
    end

    def swap(n, pn)
        @q[n], @q[pn] = @q[pn], @q[n]
    end

    def min
        @q.first
    end

    def extract_min!
        m, @q[0] = @q.first, @q.last
        @q.pop
        bubble_down(0)
        m
    end
 
    def bubble_down(n)
        c = young_child(n)
        min_index = n

        0.upto(1) { |i| min_index = c+i if ((c+i) <= @q.size-1) &&(@q[min_index] > @q[c+i]) }

        if (min_index != n)
            swap(n, min_index)
            bubble_down(min_index)
        end
    end

    def sort!
        a = []
        while v = extract_min! do a << v end
        a
    end
end

h = Heap.new([12, 14, 6, 10, 8, 27, 1, 4, 9])
puts "extract_min! = #{h.extract_min!}"
puts "extract_min! = #{h.extract_min!}"
puts "extract_min! = #{h.extract_min!}"
puts "extract_min! = #{h.extract_min!}"
puts "min = #{h.min}"
puts "min = #{h.min}"
puts "sort! = #{h.sort!}"

Let me know if you have any questions or comments and if you make improvements, post those too.