Maxiphobic Heaps

September 28, 2010

Priority queues are a data structure in which items arrive in random order and exit in priority order; they provide the operations find-min, delete-min, insert and merge. We implemented priority queues using leftist heaps in one exercise and using pairing heaps in another exercise. In today’s exercise, we will implement priority queues using the maxiphobic heaps of Chris Okasaki.

Maxiphobic heaps are a variant of leftist heaps. Like leftist heaps, maxiphobic heaps are represented as binary trees arranged according to the heap property that every element is less than or equal to its two children. Find-min looks at the root of the tree, delete-min discards the root and merges its two children, and insert merges the existing tree with a singleton tree containing the new element.

The key to leftist trees and maxiphobic trees is the merge operation. In leftist trees, the rank of each left child is always less than the rank of its sibling, where the rank of a node is defined as the length of its right spine, and the merge operation enforces this invariant. In maxiphobic trees, the merge operation is implemented by comparing the roots of the two trees. The smaller root survives as the root of the merged tree. That leaves three sub-trees: the tree that lost in the comparison of the two roots, and the child sub-trees of the winner. They are merged by first merging the two smaller trees, where the size of a tree is determined as the number of elements it contains, then attaching that merged tree along with the remaining tree as the children of the new root. The name maxiphobic, meaning “biggest avoiding,” refers to the merge of the two smaller sub-trees.

Your task is to write functions that implement maxiphobic trees. 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

2 Responses to “Maxiphobic Heaps”

  1. slabounty said

    Here’s a ruby version from the psuedo code here (http://www.eecs.usma.edu/webs/people/okasaki/sigcse05.pdf)

    class Maxiphobic
    
        class Heap
            attr_reader :value
            attr_accessor :size, :left, :right
            def initialize(value)
                @value = value
                @size = 1
                @left = nil
                @right = nil
            end
        end
    
        # Return the minimum of the heap or nil if the
        # heap is nil.
        def find_minimum
            return @heap != nil ? @heap.value : nil  
        end
    
        # Delete the minimum (root) if the heap is not nil.
        def delete_minimum
            @heap = merge(@heap.left, @heap.right) if @heap != nil 
        end
    
        # Insert a new value into the heap. Create a new
        # heap and then set the heap to either the new heap
        # of a merge of the existing and new heaps.
        def insert(v)
            new_heap = Heap.new(v)
            @heap = (@heap == nil) ? new_heap : merge(@heap, new_heap)
        end
    
        # Merge two heaps.
        def merge(h1, h2)
    
            # Return the other if either of the
            # two heaps are nil.
            return h2 if h1 == nil
            return h1 if h2 == nil
    
            # Swap so that we have the smallest
            # value in h1.
            if h2.value < h1.value
                h1, h2 = h2, h1
            end
    
            # Get the sizes of the heap and the left and right
            # sub-trees.
            h1.size = h1.size + h2.size
            a = h1.left
            a_size = (a != nil) ? a.size : 0
            b = h1.right
            b_size = (b != nil) ? b.size : 0
            c = h2
            c_size = (c != nil) ? c.size : 0
    
            # Put the smaller tree in a
            a, b = b, a if b_size > a_size 
            a, c = c, a if c_size > a_size
                
            # Set the left subtree to the smallest and 
            # then merge the other two subtrees.
            h1.left = a
            h1.right = merge(b, c)
    
            # return the merged trees in h1
            return h1
        end
    
        # Return the sorted values and empty the
        # heap.
        def sort!
            s = []
            while (v = find_minimum) != nil do
                s << v
                delete_minimum
            end
            return s
        end
    end
    
    
    maxiphobic = Maxiphobic.new
    
    [3, 1, 7, 2, 5, 6, 4].each do |v|
        maxiphobic.insert(v)
    end
    
    s = maxiphobic.sort!
    p s
    

    It works, but it seems like it could be improved quite a bit though.

  2. slabounty said

    As a side note, the ruby version should work with any objects that support “” for sorting as in …

    %w[ goodbye hello test alpha gamma beta delta].each do |v|
        maxiphobic.insert(v)
    end
    s = maxiphobic.sort!
    p s
    

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 627 other followers

%d bloggers like this: