```Sorry if this is too late to be a legitimate entry.

James, what is the official way to submit an entry?  If posting to the
list is good enough, here you go.  :-)

My solution doesn't use recursion.  It deterministically transforms
(heapindex, heapsize) coordinates into (x, y) coordinates.  My only
gripe with this solution is that pre-initializing a 2D text buffer
beforehand looks kinda kludgy.

My full solution is at http://www.shinybit.com/ruby_quiz_40.rb , but
it's just the original code from James (with the bugfix addendum) with
three methods added.  They are poorly named and could use some cleaning
up.  Here is my output, followed by the three methods I added to the
Heap class.

I've used some kludgy mechanisms in my code.  I would *love* to hear any
input on how to clean them up.  If you spot an obviously missing Ruby

The output:

,- 35
,- 29
|   `- 40
,- 20
|   |   ,- 26
|   `- 23
|       `- 51
12
|       ,- 19
|   ,- 17
|   |
`- 15
|
`- 22
,- 35
,- 29
|   `- 40
,- 20
|   |   ,- 26
|   `- 23
|       `- 51
12
|       ,- 19
|   ,- 15
|   |   `- 17
`- 13
|
`- 22
,- 35
,- 29
|   `- 40
,- 20
|   |   ,- 26
|   `- 23
|       `- 51
13
|       ,- 19
|   ,- 17
|   |
`- 15
|
`- 22

And here are the three methods I added to the Heap class:

# One bit of kludginess: The /= operator breaks indenting in emacs
# ruby-mode.  This is why I use the x = x / 2 form instead.

# ----------------------------------------------------------------------
# get_depth
#
# returns the depth in the tree of a given 0-based index.
# num - 1-based index of element.
# returns - depth of the tree at this index.  The root node has a
# depth of zero.
def get_depth(num)
(Math.log(num)/Math.log(2)).to_i
end

# ----------------------------------------------------------------------
# get_line
#
# for index num in a heap of depth rows, returns the line.
# num is 1-based index of element.
# returns 0-based line number, with 0 at the top (left-hand
# side).  Sample tree, get_line(1) returns 7, etc.
def get_line(num)
depth = get_depth(@heap.length)
# Okay, scary algorithm.  Odd-numbered indexes are down from their
# parents while even-numbered indexes are up from their parents.
# We want to move from this node, up the tree to the root,
# considering each node for even/oddness.  At the leafmost level,
# the leaves move up or down 1 line.  Each level you move up, the
# offset doubles, until node 1 is moved down 1/2 the size of the
# tree (because it's odd).
line = 0
while num > 0
offset = 2**(depth - get_depth(num))
if num % 2 == 1
line += offset
else
line -= offset
end
num = num / 2 # Integer divide to get parent index.
end
line-1
end

# ----------------------------------------------------------------------
# to_s
#
# converts the heap to an ascii art tree representation.
def to_s
output = []

# Initialize output as an array of strings.  We're going to "draw"
into the
# output like it's a 2D text buffer, so we need to make sure the
output is
# initialized with indent strings.  (By an odd coincidence, all of
ascii art
# is confined to the area to the left of each given string.
However, some
# elements are empty, so we need to make sure that all lines have
their left
#
# This hairy bit of math calculates the next largest power of 2 up
from @heap.length.
max_lines = 2**((Math.log(@heap.length)/Math.log(2)).to_i + 1)
max_indent = get_depth(max_lines)

(@heap.length).times { output.push(' ' * INDENT_AMOUNT * max_indent) }

@heap.each_with_index do |item, index|
next if index.zero?  # @heap[0] appears to be a dummy node
output[get_line(index)] = ' ' * INDENT_AMOUNT * get_depth(index) +
item.to_s
end

# Okay, the tree nodes are now "drawn" into the output buffer.
# Now draw connecting lines.  At each child node, draw ,- or `-
# into their left margin.  Then bring down a column of |'s to
# the parent node.
#
# Note that since we're drilling "down" from the parent nodes, we
# only need to traverse the first half of the items in the tree.
# The careful observer might note that in the sample tree, node 7
# ("22") never gets traversed.  This is okay; it gets skipped
# because we know it can't possibly have any children.
(@heap.length / 2).times do |i|
j = i+1 # The math is easier when done 1-based.

# this whole mess could be refactored; these 2 blocks
# differ only in start line, ,- vs `- text, and loop
# direction.

# connect node i to node i*2 (up from parent)
indent = get_depth(j*2) * INDENT_AMOUNT
stop_line = get_line(j)

next if j*2 >= @heap.length

start_line = get_line(j*2)
output[start_line][indent-3..indent-2] = ',-'
start_line += 1
while start_line < stop_line
output[start_line][indent-3] = '|'
start_line += 1
end

# connect node i to node i*2+1 (down from parent)
start_line = get_line(j*2+1)
indent = get_depth(j*2+1) * INDENT_AMOUNT
next if j*2+1 >= @heap.length

output[start_line][indent-3..indent-2] = '`-'
start_line -= 1
while start_line > stop_line
output[start_line][indent-3] = '|'
start_line -= 1
end
end

output.join("\n")
end

Cheers!

-dB

--