Class: Timers::PriorityHeap

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

Overview

A priority queue implementation using a standard binary minheap. It uses straight comparison of its contents to determine priority. This works because a Handle from Timers::Events implements the ‘<’ operation by comparing the expiry time. See <en.wikipedia.org/wiki/Binary_heap> for explanations of the main methods.

Instance Method Summary collapse

Constructor Details

#initialize ⇒ PriorityHeap

Returns a new instance of PriorityHeap.



30
31
32
33
34
35
 
# File 'lib/timers/priority_heap.rb', line 30

def initialize
	# The heap is represented with an array containing a binary tree. See
	# https://en.wikipedia.org/wiki/Binary_heap#Heap_implementation for how this array
	# is built up.
	@contents = []
end

Instance Method Details

#peek ⇒ Object

Returns the earliest timer or nil if the heap is empty.



38
39
40
 
# File 'lib/timers/priority_heap.rb', line 38

def peek
	@contents[0]
end

#pop ⇒ Object

Returns the earliest timer if the heap is non-empty and removes it from the heap. Returns nil if the heap is empty. (and doesn’t change the heap in that case)



49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
 
# File 'lib/timers/priority_heap.rb', line 49

def pop
	# If the heap is empty:
	if @contents.empty?
		return nil
	end
	
	# If we have only one item, no swapping is required:
	if @contents.size == 1
		return @contents.pop
	end
	
	# Take the root of the tree:
	value = @contents[0]
	
	# Remove the last item in the tree:
	last = @contents.pop
	
	# Overwrite the root of the tree with the item:
	@contents[0] = last
	
	# Bubble it down into place:
	bubble_down(0)
	
	# validate!
	
	return value
end

#push(element) ⇒ Object

Inserts a new timer into the heap, then rearranges elements until the heap invariant is true again.



78
79
80
81
82
83
84
85
86
87
88
 
# File 'lib/timers/priority_heap.rb', line 78

def push(element)
	# Insert the item at the end of the heap:
	@contents.push(element)
	
	# Bubble it up into position:
	bubble_up(@contents.size - 1)
	
	# validate!
	
	return self
end

#size ⇒ Object

Returns the number of elements in the heap



43
44
45
 
# File 'lib/timers/priority_heap.rb', line 43

def size
	@contents.size
end