```On Fri, 22 Jul 2005 15:05:26 +0200, Ruby Quiz <james / grayproductions.net>
wrote:

> In fact, here's a basic pure Ruby implementation (not exhaustively
> tested) using the system I just described:

I found two problems ;-)

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

This doesn't really extract the last element...

> 	def sift_down(  )
...
> 			c += 1 if c + 1 < @heap.size and @heap[c + 1] < @heap[c]

You probably wanted to say:
c += 1 if c + 1 < @heap.size and @comp[@heap[c + 1], @heap[c]] < 0

So, here is my solution. It draws the subtrees recursively and merges the
results.

Here are some examples:

\$ ruby heap.rb
12
|
+--+-----+
|        |
20       15
|        |
+--+--+   +-++
|     |   |  |
29    23   17 22
|     |   |
+-++  +-++  +
|  |  |  |  |
35 40 26 51 19

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

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

\$ ruby -r heap.rb -e 'puts Heap.new(*((1..45).to_a))'
1
|
+-----------+----------------------+
|                                  |
2                                  3
|                                  |
+---------+-----------+                +-----+-----+
|                     |                |           |
4                     5                6           7
|                     |                |           |
+-----+-----+           +---+-----+       +--+--+     +--+--+
|           |           |         |       |     |     |     |
8           9          10         11     12    13    14    15
|           |           |         |       |     |     |     |
+--+--+     +--+--+     +--+--+     ++--+  +-++  +-++  +-++  +-++
|     |     |     |     |     |     |   |  |  |  |  |  |  |  |  |
16    17    18    19    20    21    22   23 24 25 26 27 28 29 30 31
|     |     |     |     |     |     |
+-++  +-++  +-++  +-++  +-++  +-++  +-++
|  |  |  |  |  |  |  |  |  |  |  |  |  |
32 33 34 35 36 37 38 39 40 41 42 43 44 45

\$ ruby -r heap.rb -e 'puts Heap.new(*(%w(aaaaaaa bbbb ccccccccccccc dddddd
ee fffff gg)))'
aaaaaaa
|
+------+----+
|           |
bbbb    ccccccccccccc
|           |
+-+--+      +-+-+
|    |      |   |
dddddd ee   fffff gg

And here is the code:

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

clear
insert(*elements)
end

def clear
@heap = [nil]
end

def extract
case size <=> 1
when -1
nil
when 0
@heap.pop
else
extracted = @heap[1]
@heap[1] = @heap.pop
sift_down
extracted
end
end

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

def size
@heap.size - 1
end

def empty?
@heap.size == 1
end

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

def to_s
if empty?
"[empty heap]"
else
res, = to_s_rec(1)
res.shift
res.join "\n"
end
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 @comp[@heap[c + 1], @heap[c]]
< 0
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
while 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

# rows1 and rows2 are arrays of strings (ascii-art), this method will
merge
# those into one array of strings.
# The strings from rows1 / rows2 will start at p1 / p2 in the result.
#
# ex: merge_rows(["a", "b"], ["c", "d"], 1, 3) => [" a c", " b d"]
# ex: merge_rows(["a", "b"], [], 1, 3) => [" a", " b"]
# ex: merge_rows([], ["c", "d"], 1, 3) => ["   c", "   d"]
def merge_rows(rows1, rows2, p1, p2)
i = 0
res = []
while i < rows1.size || i < rows2.size
res << " " * p1
res.last << rows1[i] if i < rows1.size
if i < rows2.size
res.last << " " * [0, p2 - res.last.size].max
res.last << rows2[i]
end
i += 1
end
res
end

# builds an ascii-art representation of the subtree starting at index
# i in @heap
#
# returns two values: an array of strings (the ascii-art) and the
length of
# the longest string in that array (the width of the ascii-art)
def to_s_rec(i)
str = @heap[i].to_s
str = " " if str.empty?

if i*2 < @heap.size # has left child
l, wl = to_s_rec(i*2)
else
return [["|".center(str.size) , str], str.size]
end

if i*2+1 < @heap.size # has right child
r, wr = to_s_rec(i*2+1)
else
r, wr = [], -1
end

# merge the subtree ascii-arts
sumw = wl + wr + 1
w = [sumw, str.size].max
indent = (w - sumw) / 2
res = merge_rows(l, r, indent, indent + wl + 1)

# build the connection between parent and children
# the vertical bar:
vert = "|".center(w)

# the horizontal connection e.g. "+--+--+"
con = res[0].gsub("|", "+")
con[vert.index("|")] = ?+
# convert spaces between pluses to minuses
con.sub!(/\+(.+)\+/) { |s| s.gsub(" ", "-") }

# put it all together
[[vert, str.center(w), vert, con] + res, w]
end

end

if \$0 == __FILE__
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

```