1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
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
140
141
142
143
144
145
146
147
|
# frozen_string_literal: true
# Released under the MIT License.
# Copyright, 2021, by Wander Hillen.
# Copyright, 2021-2025, by Samuel Williams.
module Timers
# 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 <https://en.wikipedia.org/wiki/Binary_heap> for explanations of the main methods.
class PriorityHeap
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
# Returns the earliest timer or nil if the heap is empty.
def peek
@contents[0]
end
# Returns the number of elements in the heap
def size
@contents.size
end
# 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)
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
# Inserts a new timer into the heap, then rearranges elements until the heap invariant is true again.
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
# Empties out the heap, discarding all elements
def clear!
@contents = []
end
# Validate the heap invariant. Every element except the root must not be smaller than
# its parent element. Note that it MAY be equal.
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
private
# Left here for reference, but unused.
# def swap(i, j)
# @contents[i], @contents[j] = @contents[j], @contents[i]
# end
def bubble_up(index)
parent_index = (index - 1) / 2 # watch out, integer division!
while index > 0 && @contents[index] < @contents[parent_index]
# if the node has a smaller value than its parent, swap these nodes
# to uphold the minheap invariant and update the index of the 'current'
# node. If the node is already at index 0, we can also stop because that
# is the root of the heap.
# swap(index, parent_index)
@contents[index], @contents[parent_index] = @contents[parent_index], @contents[index]
index = parent_index
parent_index = (index - 1) / 2 # watch out, integer division!
end
end
def bubble_down(index)
swap_value = 0
swap_index = nil
while true
left_index = (2 * index) + 1
left_value = @contents[left_index]
if left_value.nil?
# This node has no children so it can't bubble down any further.
# We're done here!
return
end
# Determine which of the child nodes has the smallest value:
right_index = left_index + 1
right_value = @contents[right_index]
if right_value.nil? or right_value > left_value
swap_value = left_value
swap_index = left_index
else
swap_value = right_value
swap_index = right_index
end
if @contents[index] < swap_value
# No need to swap, the minheap invariant is already satisfied:
return
else
# At least one of the child node has a smaller value than the current node, swap current node with that child and update current node for if it might need to bubble down even further:
# swap(index, swap_index)
@contents[index], @contents[swap_index] = @contents[swap_index], @contents[index]
index = swap_index
end
end
end
end
end
|
