Class: Vines::Services::PriorityQueue::Heap

Inherits:
Object
  • Object
show all
Defined in:
lib/vines/services/priority_queue.rb

Overview

A binary min heap implementation for efficient storage of queue items. This class implements the Array methods called by EM::Queue so that it may replace the @items instance variable. Namely, push shift, size, and empty? are implemented.

Instance Method Summary collapse

Constructor Details

#initialize(*items, &comp) ⇒ Heap

Returns a new instance of Heap.



38
39
40
41
42
 
# File 'lib/vines/services/priority_queue.rb', line 38

def initialize(*items, &comp)
  @heap = []
  @comp = comp || proc {|a, b| a <=> b }
  push(*items)
end

Instance Method Details

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


66
67
68
 
# File 'lib/vines/services/priority_queue.rb', line 66

def empty?
  @heap.empty?
end

#pop ⇒ Object Also known as: shift 



52
53
54
55
56
57
58
59
 
# File 'lib/vines/services/priority_queue.rb', line 52

def pop
  return if @heap.empty?
  root = @heap[0]
  @heap[0] = @heap[-1]
  @heap.pop
  move_down(0)
  root
end

#push(*items) ⇒ Object Also known as: << 



44
45
46
47
48
49
 
# File 'lib/vines/services/priority_queue.rb', line 44

def push(*items)
  items.each do |item|
    @heap << item
    move_up(@heap.size - 1)
  end
end

#size ⇒ Object 



62
63
64
 
# File 'lib/vines/services/priority_queue.rb', line 62

def size
  @heap.size
end