Skip to content

Instantly share code, notes, and snippets.

@alanjcfs
Created August 27, 2011 00:02
Show Gist options
  • Save alanjcfs/1174739 to your computer and use it in GitHub Desktop.
Save alanjcfs/1174739 to your computer and use it in GitHub Desktop.
An attempt at implementing Priority Queue through solely Ruby
class Binary_heap
def initialize(num = 10)
@ary = Array.new
num.times do @ary << rand(100) end
end
attr_reader :items, :ary
def binary_heap()
@ary.unshift(nil)
end
def build_heap()
i = (@ary.size() - 1)/2
begin
percolate_down(i)
i -= 1
end until i <= 1
end
def percolate_down(hole)
tmp = @ary[hole]
begin
child = hole * 2
if (child != @ary.size && @ary[child+1] < @ary[child])
child += 1
end
if (@ary[child] < tmp)
@ary[hole] = @ary[child]
else break
end
hole = child
end while (hole*2 <= @ary.size)
@ary[hole] = tmp
end
end
heap = Binary_heap.new
puts heap.ary
heap.binary_heap
puts heap.ary
heap.build_heap
puts heap.ary
@alanjcfs
Copy link
Author

I am not sure why it doesn't work. Why does @ary[child] return nil when it should return the element in the array?

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