Class: PriorityQueue

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(&prc) ⇒ PriorityQueue

Returns a new instance of PriorityQueue.



7
8
9
10
 
# File 'lib/priority_queue.rb', line 7

def initialize(&prc)
  @store = Array.new
  @prc = prc || Proc.new { |el1, el2| el1 <=> el2 }
end

Instance Attribute Details

#store ⇒ Object (readonly)

Returns the value of attribute store.



5
6
7
 
# File 'lib/priority_queue.rb', line 5

def store
  @store
end

Instance Method Details

#extract ⇒ Object 



17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
# File 'lib/priority_queue.rb', line 17

def extract
  raise "PriorityQueue is empty" if @store.empty?

  value, _ = @store[0]

  if @store.length > 1
    @store[0] = @store.pop
    self.heapify_down(0)
  else
    @store.pop
  end

  value
end

#find_children(idx) ⇒ Object 



67
68
69
70
71
72
 
# File 'lib/priority_queue.rb', line 67

def find_children(idx)
  child_1 = (idx * 2) + 1
  child_2 = (idx * 2) + 2

  return [child_1, child_2].select { |i| i < @store.length }
end

#find_parent(idx) ⇒ Object 



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

def find_parent(idx)
  return false if idx == 0
  return (idx - 1) / 2
end

#heapify_down(start_idx) ⇒ Object 



45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
# File 'lib/priority_queue.rb', line 45

def heapify_down(start_idx)
  children_idx = find_children(start_idx)
  children_idx.select! { |i| i < @store.length }

  return true if children_idx.all? { |i| @prc.call(@store[i][1], @store[start_idx][1]) >= 0 }

  if children_idx.length == 1
    temp_idx = children_idx[0] 
  else
    temp_idx = @prc.call(@store[children_idx[0]][1], @store[children_idx[1]][1]) == -1 ? children_idx[0] : children_idx[1]
  end

  @store[temp_idx], @store[start_idx] = @store[start_idx], @store[temp_idx]

  heapify_down(temp_idx)
end

#heapify_up(start_idx) ⇒ Object 



32
33
34
35
36
37
38
39
40
41
42
43
 
# File 'lib/priority_queue.rb', line 32

def heapify_up(start_idx)
  return true if start_idx == 0

  parent_idx = find_parent(start_idx)

  if @prc.call(@store[start_idx][1], @store[parent_idx][1]) == -1
    @store[start_idx], @store[parent_idx] = @store[parent_idx], @store[start_idx]
    heapify_up(parent_idx)
  else
    return true
  end
end

#insert(val, priority) ⇒ Object 



12
13
14
15
 
# File 'lib/priority_queue.rb', line 12

def insert(val, priority)
  @store << [val, priority]
  self.heapify_up(@store.length - 1)
end