Maxiphobic Heaps

September 28, 2010

A maxiphobic heap is a binary tree with node defined as four-slot vectors:

(define mh-node vector) ; size item lkid rkid

Four functions provide access to the four slots of the vector; they are defined as macros so they will be inlined:

(define-syntax mh-size (syntax-rules () ((_ mh) (vector-ref mh 0))))
(define-syntax mh-item (syntax-rules () ((_ mh) (vector-ref mh 1))))
(define-syntax mh-lkid (syntax-rules () ((_ mh) (vector-ref mh 2))))
(define-syntax mh-rkid (syntax-rules () ((_ mh) (vector-ref mh 3))))

There is a single, distinguished node representing the empty priority queue, with size zero, and a predicate to identify it:

(define mh-empty (mh-node 0 'mh-empty 'mh-empty 'mh-empty))
(define (mh-empty? mh) (eqv? mh mh-empty))

The fundamental operation is merge:

(define (mh-merge lt? mh1 mh2)
  (cond ((mh-empty? mh1) mh2) ((mh-empty? mh2) mh1)
  (else (if (lt? (mh-item mh1) (mh-item mh2))
            (let ((mhs (mh-biggest (mh-lkid mh1) (mh-rkid mh1) mh2)))
              (mh-node (+ (mh-size mh1) (mh-size mh2))
                       (mh-item mh1) (car mhs)
                       (apply mh-merge lt? (cdr mhs))))
            (let ((mhs (mh-biggest mh1 (mh-lkid mh2) (mh-rkid mh2))))
              (mh-node (+ (mh-size mh1) (mh-size mh2))
                       (mh-item mh2) (car mhs)
                       (apply mh-merge lt? (cdr mhs))))))))

The merge function first checks for the trivial cases where one or the other maxiphobic heap is empty. If not, it compares the items at the roots of the two trees and merges them according to the algorithm. Merge calls an auxiliary function mh-biggest to determine which sub-trees to merge first:

(define (mh-biggest mh1 mh2 mh3)
  (if (< (mh-size mh1) (mh-size mh2))
         (if (< (mh-size mh2) (mh-size mh3))
             (list mh3 mh1 mh2)
             (list mh2 mh1 mh3))
         (if (< (mh-size mh1) (mh-size mh3))
             (list mh3 mh1 mh2)
             (list mh1 mh2 mh3))))

Given merge, insert, find-min and delete are trivial, and are identical to their leftist-heap counterparts:

(define (mh-insert lt? x mh)
  (mh-merge lt? (mh-node 1 x mh-empty mh-empty) mh))

(define (mh-find-min mh)
  (if (mh-empty? mh)
      (error 'mh-find-min "empty maxiphobic heap")
      (mh-item mh)))

(define (mh-delete-min lt? mh)
  (if (mh-empty? mh)
      (error 'mh-delete-min "empty maxiphobic heap")
      (mh-merge lt? (mh-lkid mh) (mh-rkid mh))))

To illustrate maxiphobic heaps, we provide this sorting function that inserts each of its inputs into a maxiphobic heap, in random input order, and outputs them in priority order:

(define (mh-sort lt? xs)
  (let loop1 ((xs xs) (mh mh-empty))
    (if (pair? xs)
        (loop1 (cdr xs) (mh-insert lt? (car xs) mh))
        (let loop2 ((mh mh) (zs '()))
          (if (mh-empty? mh)
              (reverse zs)
              (loop2 (mh-delete-min lt? mh)
                     (cons (mh-find-min mh) zs)))))))

Here’s an example:

> (mh-sort > '(3 1 7 2 5 6 4))
(7 6 5 4 3 2 1)

You can run the program at http://programmingpraxis.codepad.org/YZIkmZ02.

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

%d bloggers like this: