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.

Constant Summary collapse

HEAPIFY_INSERT_RATIO = 
2

Instance Method Summary collapse

Constructor Details

#initialize ⇒ PriorityHeap

Initializes the heap.



16
17
18
19
20
21
 
# File 'lib/io/event/priority_heap.rb', line 16

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



118
119
120
 
# File 'lib/io/event/priority_heap.rb', line 118

def clear!
	@contents = []
end

#concat(elements) ⇒ Object

Add multiple elements to the heap efficiently.



88
89
90
91
92
93
94
95
96
97
98
99
100
 
# File 'lib/io/event/priority_heap.rb', line 88

def concat(elements)
	return self if elements.empty?
	
	# Rebuilding the whole heap is `O(n + m)`, where `n` is the existing heap size and `m` is the appended batch size. Incremental `push` is `O(m log(n))`, but is often closer to `O(m)` when appended elements are later than the existing entries and do not bubble far. Prefer `heapify` only when building from empty or when the batch dominates the existing heap.
	if @contents.empty? || elements.size > @contents.size * HEAPIFY_INSERT_RATIO
		@contents.concat(elements)
		heapify!
	else
		elements.each{|element| push(element)}
	end
	
	return self
end

#delete(element) ⇒ Object

Remove a specific element from the heap.

O(n) where n is the number of elements in the heap.



128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
 
# File 'lib/io/event/priority_heap.rb', line 128

def delete(element)
	# Find the index of the element - O(n) linear search
	index = @contents.index(element)
	return nil unless index
	
	# If it's the last element, just remove it
	if index == @contents.size - 1
		return @contents.pop
	end
	
	# Store the value we're removing
	removed_value = @contents[index]
	
	# Replace with the last element
	last = @contents.pop
	@contents[index] = last
	
	# Restore heap property - might need to bubble up or down
	if index > 0 && @contents[index] < @contents[(index - 1) / 2]
		# New element is smaller than parent, bubble up
		bubble_up(index)
	else
		# New element might be larger than children, bubble down
		bubble_down(index)
	end
	
	# validate!
	
	return removed_value
end

#delete_if ⇒ Object

Remove elements matching the given block condition by rebuilding the heap.

This is more efficient than multiple delete operations when removing many elements.

O(n) where n is the number of elements in the heap.



167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
 
# File 'lib/io/event/priority_heap.rb', line 167

def delete_if
	return enum_for(:delete_if) unless block_given?
	
	original_size = @contents.size
	
	# Filter out elements that match the condition - O(n)
	@contents.reject!{|element| yield(element)}
	
	# If we removed elements, rebuild the heap - O(n)
	if @contents.size < original_size
		heapify!
	end
	
	# Return number of elements removed
	original_size - @contents.size
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


34
35
36
 
# File 'lib/io/event/priority_heap.rb', line 34

def empty?
	@contents.empty?
end

#heapify {|@contents| ... } ⇒ Object

Mutate the heap contents directly, then rebuild the heap property.

This supports batched operations that can be completed with a single ‘O(n)` heapify instead of multiple `O(log n)` heap operations.

Yields:

  • (@contents) 


108
109
110
111
112
113
114
115
 
# File 'lib/io/event/priority_heap.rb', line 108

def heapify
	yield @contents
	
	# The block may arbitrarily append, delete or reorder contents, so repair the invariant with one `O(n)` bottom-up heapify pass.
	heapify!
	
	return self
end

#peek ⇒ Object 



24
25
26
 
# File 'lib/io/event/priority_heap.rb', line 24

def peek
	@contents[0]
end

#pop ⇒ Object

Removes and returns the smallest element in the heap, or nil if the heap is empty.



41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
 
# File 'lib/io/event/priority_heap.rb', line 41

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

Add a new element to the heap, then rearrange elements until the heap invariant is true again.



72
73
74
75
76
77
78
79
80
81
82
 
# File 'lib/io/event/priority_heap.rb', line 72

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 



29
30
31
 
# File 'lib/io/event/priority_heap.rb', line 29

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) 


185
186
187
188
 
# File 'lib/io/event/priority_heap.rb', line 185

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