Skip to content

Instantly share code, notes, and snippets.

@aspyct
Created August 22, 2012 19:42
  • Star 1 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save aspyct/3428688 to your computer and use it in GitHub Desktop.
Binomial heap (priority queue) implementation in ruby
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
@derat
Copy link

derat commented Dec 31, 2012

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment