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

Initializes the heap.



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

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



100
101
102
 
# File 'lib/io/event/priority_heap.rb', line 100

def clear!
	@contents = []
end

#concat(elements) ⇒ Object

Add multiple elements to the heap efficiently in O(n) time. This is more efficient than calling push multiple times (O(n log n)).



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

def concat(elements)
	return self if elements.empty?
	
	# Add all elements to the array without maintaining heap property - O(n)
	@contents.concat(elements)
	
	# Rebuild the heap property for the entire array - O(n)
	heapify!
	
	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.



110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
 
# File 'lib/io/event/priority_heap.rb', line 110

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.



149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
 
# File 'lib/io/event/priority_heap.rb', line 149

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) 


32
33
34
 
# File 'lib/io/event/priority_heap.rb', line 32

def empty?
	@contents.empty?
end

#peek ⇒ Object 



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

def peek
	@contents[0]
end

#pop ⇒ Object

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



39
40
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
 
# File 'lib/io/event/priority_heap.rb', line 39

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.



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

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 



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

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) 


167
168
169
170
 
# File 'lib/io/event/priority_heap.rb', line 167

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