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