class DSA::PriorityQueue

priority queue built on top of array based heap

Public Class Methods

new() click to toggle source
# File lib/DSA/priority_queue.rb, line 11
def initialize
  @data = Array.new
end

Public Instance Methods

add(priority, element) click to toggle source

priority is a number, the smaller it is, higher it has a priority

# File lib/DSA/priority_queue.rb, line 26
def add(priority, element)
  @data.push PriorityQueueNode.new(priority,element)
  up_heap_bubbling length-1
end
length() click to toggle source
# File lib/DSA/priority_queue.rb, line 15
def length
  @data.length
end
pop() click to toggle source

remove the top and return the element

# File lib/DSA/priority_queue.rb, line 32
def pop
  value = top
  @data[0] = @data.pop # move the rightmost node to the top
  down_heap_sinking 0
  value
end
top() click to toggle source

get the value of the top without removing it

# File lib/DSA/priority_queue.rb, line 20
def top
  return nil if length == 0
  @data.first.element
end

Private Instance Methods

down_heap_sinking(index) click to toggle source
# File lib/DSA/priority_queue.rb, line 53
def down_heap_sinking(index)
  left_child_index = 2*index + 1
  right_child_index = 2*index + 2
  small_child_index = index
  if left_child_index < length
    small_child_index = left_child_index if @data[left_child_index].priority < @data[small_child_index].priority
  end
  if right_child_index < length
    small_child_index = right_child_index if @data[right_child_index].priority < @data[small_child_index].priority
  end
  if small_child_index != index
    swap small_child_index, index
    down_heap_sinking small_child_index
  end
end
swap(index_a, index_b) click to toggle source
# File lib/DSA/priority_queue.rb, line 49
def swap(index_a, index_b)
  @data[index_a], @data[index_b] = @data[index_b], @data[index_a]
end
up_heap_bubbling(index) click to toggle source
# File lib/DSA/priority_queue.rb, line 40
def up_heap_bubbling(index)
  parent_index = (index - 1) / 2
  return if parent_index < 0
  if @data[index].priority < @data[parent_index].priority
    swap index, parent_index
    up_heap_bubbling parent_index
  end
end