class Priorityq::Heap
Attributes
heap[R]
Public Class Methods
max()
click to toggle source
# File lib/priorityq/heap.rb, line 9 def self.max new end
min()
click to toggle source
# File lib/priorityq/heap.rb, line 13 def self.min MinHeap.new end
new()
click to toggle source
# File lib/priorityq/heap.rb, line 17 def initialize @heap = [0] end
Public Instance Methods
empty?()
click to toggle source
# File lib/priorityq/heap.rb, line 21 def empty? heap.size == 1 end
peek()
click to toggle source
# File lib/priorityq/heap.rb, line 25 def peek return nil if empty? heap[1] end
pop()
click to toggle source
# File lib/priorityq/heap.rb, line 31 def pop return nil if empty? exchange 1, top value = heap.pop bubble_down 1 value end
push(value)
click to toggle source
# File lib/priorityq/heap.rb, line 40 def push(value) heap.push value bubble_up top end
Private Instance Methods
bubble_down(index)
click to toggle source
# File lib/priorityq/heap.rb, line 49 def bubble_down(index) largest = largest_child_index(index) return if largest.nil? || in_order?(index, largest) exchange index, largest bubble_down largest end
bubble_up(index)
click to toggle source
# File lib/priorityq/heap.rb, line 57 def bubble_up(index) return if index == 1 pi = parent_index(index) return if in_order?(pi, index) exchange index, pi bubble_up pi end
exchange(first_index, second_index)
click to toggle source
# File lib/priorityq/heap.rb, line 68 def exchange(first_index, second_index) first_value = heap[first_index] second_value = heap[second_index] heap[first_index] = second_value heap[second_index] = first_value end
in_order?(first_index, second_index)
click to toggle source
# File lib/priorityq/heap.rb, line 75 def in_order?(first_index, second_index) heap[first_index] >= heap[second_index] end
largest_child_index(index)
click to toggle source
# File lib/priorityq/heap.rb, line 79 def largest_child_index(index) max = top left = 2 * index return if left > max right = left + 1 return left if right > max || in_order?(left, right) right end
parent_index(child_index)
click to toggle source
# File lib/priorityq/heap.rb, line 90 def parent_index(child_index) (child_index / 2).floor end
top()
click to toggle source
# File lib/priorityq/heap.rb, line 94 def top heap.size - 1 end