public
Last active

Binomial heap (priority queue) implementation in ruby

  • Download Gist
heap.rb
Ruby
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 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98
class Heap
def initialize
# @elements is an array representing the tree
# for each i:
# parent => @elements[i / 2]
# left => @elements[i * 2]
# right => @elements[i * 2 + 1]
@elements = []
end
 
def empty
return @elements.count == 0
end
 
def pop_min
value = @elements[0].first
 
# Replace the [0]th element with the last one and bubble it down
pair = @elements.pop
 
# If it was the last element of the array, abort anyway
if @elements.count > 0
@elements[0] = pair
self.bubble_down pair, 0
end
 
return value
end
 
def peek_min
return @elements[0].first
end
 
def push(object, order)
# Put the element at the end of the array and bubble it up the tree
offset = @elements.count
pair = [object, order]
@elements << pair
 
self.bubble_up pair, offset
end
 
def bubble_up(pair, offset)
# Push an element up the tree, if need be
parent = offset / 2
 
while (offset > 0 && @elements[parent].last > pair.last)
@elements[parent], @elements[offset] = @elements[offset], @elements[parent]
offset = parent
parent = offset / 2
end
end
 
def bubble_down(pair, offset)
# Push an element down the tree if need be
while (offset < @elements.count / 2)
offset_a = offset * 2
offset_b = offset_a + 1
 
if @elements[offset_a].last > @elements[offset_b].last
smallest = offset_b
else
smallest = offset_a
end
 
if pair.last <= @elements[smallest].last
break
end
 
@elements[offset], @elements[smallest] = @elements[smallest], @elements[offset]
offset = smallest
end
end
end
 
h = Heap.new
 
# Insert 'a' => 'o' in the heap, random order
h.push "g", 7
h.push "m", 13
h.push "k", 11
h.push "d", 4
h.push "c", 3
h.push "n", 14
h.push "b", 2
h.push "f", 6
h.push "a", 1
h.push "j", 10
h.push "i", 9
h.push "e", 5
h.push "o", 15
h.push "h", 8
h.push "l", 12
 
# Dump the heap
while !h.empty
puts h.pop_min
end

This appears to be broken.

h = Heap.new

h.push "a", 1
h.push "a", 1
h.push "a", 1
h.push "a", 1

h.pop_min
h.push "b", 2
h.pop_min
h.push "b", 2
h.pop_min
h.push "b", 2
h.pop_min
h.push "b", 2

puts h.pop_min while !h.empty

produces:

b        
b
a
b

instead of the expected:

b
b
b
b

I believe that the bug lies in the index calculations in bubble_up and bubble_down. index's parent should be at (index - 1) / 2 rather than index / 2, and its left and right children are at index * 2 + 1 and index * 2 + 2 respectively rather than index * 2 and index * 2 + 1. See e.g. http://en.wikipedia.org/wiki/Binary_heap#Heap_implementation.

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.