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:

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...