From: Ruby Quiz <james@...>
Date: 2005-07-22T22:05:26+09:00
Subject: [QUIZ] Drawing Trees (#40)

The three rules of Ruby Quiz:

1.  Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2.  Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3.  Enjoy!

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

A common implementation of Heap data structures involves storing their tree in a
single Array.  If you add one extra element at the beginning (creating a base 1
Array), you can use easy math to find child nodes. This doesn't generally bother
the user, because you don't usually access a Heap by index.

Using that system and given any index i, 2 * i is the left child node and 2 * i
+ 1 is the right child node. So the root of the tree is i = 1 and it has a child
node at i = 2 and another at i = 3.  Then the i = 2 node has child nodes at i =
4 and i = 5.  Reversing the traversal, i / 2 (assuming integer division) will
bring you to a parent node.

Now take a deep breath and relax because I'm not going to ask you to write a
Heap.  In fact, here's a basic pure Ruby implementation (not exhaustively
tested) using the system I just described:

	class Heap
		def initialize( *elements, &comp )
			@heap = [nil]
			@comp = comp || lambda { |p, c| p <=> c }

			insert(*elements)
		end

		def clear(  )
			@heap = [nil]
		end

		def extract(  )
			extracted = @heap[1]
			@heap[1] = @heap.pop unless @heap.size.zero?
			sift_down
			extracted
		end

		def insert( *elements )
			elements.each do |element|
				@heap << element
				sift_up
			end
		end

		def size(  )
			@heap.size - 1
		end

		def inspect(  )
			@heap[1..-1].inspect
		end

		def to_s(  )
			# Write this!
		end

		private

		def sift_down(  )
			i = 1
			loop do
				c = 2 * i
				break if c >= @heap.size

				c += 1 if c + 1 < @heap.size and @heap[c + 1] < @heap[c]
				break if @comp[@heap[i], @heap[c]] <= 0

				@heap[c], @heap[i] = @heap[i], @heap[c]
				i = c
			end
		end

		def sift_up(  )
			i = @heap.size - 1
			until i == 1
				p = i / 2
				break if @comp[@heap[p], @heap[i]] <= 0

				@heap[p], @heap[i] = @heap[i], @heap[p]
				i = p
			end
		end
	end

	priority_queue = Heap.new
	priority_queue.insert(12, 20, 15, 29, 23, 17, 22, 35, 40, 26, 51, 19)
	puts priority_queue

	priority_queue.insert(13)
	puts priority_queue

	priority_queue.extract
	puts priority_queue
	__END__

If you read that real closely, you saw the blank Heap.to_s() method. 
Implementing a Heap as an Array is one thing and it's easy to show like that
(see Heap.inspect() above).  However, we generally envision a Heap as a tree,
not an Array.  Wouldn't it be nice if Heap.to_s() would show it to us that way? 
I think so too.

This week's Ruby Quiz is to write Heap.to_s() so that it returns an ASCII art
representation of a Heap as a tree.  For example, here's what the first tree
printed by the above code might look like:

	              12
	               |
	       +-------+-------+
	       |               |
	      20              15
	       |               |
	   +---+---+       +---+---+
	   |       |       |       |
	  29      23      17      22
	   |       |       |
	 +-+-+   +-+-+   +-+
	 |   |   |   |   |
	35  40  26  51  19

Your tree doesn't have to look like that.  Maybe you would prefer to draw it
horizontally.  Maybe you make better looking ASCII art than me.  Whatever. 
Anything that gives a feel of the structure is fine.

Heaps don't have to hold two-digit Integers of course, any Comparable should
work...