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