Class: IO::Event::PriorityHeap

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

Overview

A priority queue implementation using a standard binary minheap. It uses straight comparison of its contents to determine priority. 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.



13
14
15
16
17
18
 
# File 'lib/io/event/priority_heap.rb', line 13

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

#clear! ⇒ Object

Empties out the heap, discarding all elements



74
75
76
 
# File 'lib/io/event/priority_heap.rb', line 74

def clear!
	@contents = []
end

#peek ⇒ Object

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



21
22
23
 
# File 'lib/io/event/priority_heap.rb', line 21

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)



32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
# File 'lib/io/event/priority_heap.rb', line 32

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.



61
62
63
64
65
66
67
68
69
70
71
 
# File 'lib/io/event/priority_heap.rb', line 61

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



26
27
28
 
# File 'lib/io/event/priority_heap.rb', line 26

def size
	@contents.size
end

#valid? ⇒ Boolean

Validate the heap invariant. Every element except the root must not be smaller than its parent element. Note that it MAY be equal.

Returns:

  • (Boolean) 


80
81
82
83
 
# File 'lib/io/event/priority_heap.rb', line 80

def valid?
	# notice we skip index 0 on purpose, because it has no parent
	(1..(@contents.size - 1)).all? { |e| @contents[e] >= @contents[(e - 1) / 2] }
end