`class PriorityHeap`

A priority queue implementation using a standard binary minheap. It uses straight comparison of its contents to determine priority. See https://en.wikipedia.org/wiki/Binary_heap for explanations of the main methods.

Definitions

`def peek`

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

Implementation

def peek
	@contents[0]
end

`def size`

Returns the number of elements in the heap

Implementation

def size
	@contents.size
end

`def pop`

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)

Implementation

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

`def push(element)`

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

Implementation

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

`def clear!`

Empties out the heap, discarding all elements

Implementation

def clear!
	@contents = []
end

`def valid?`

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

Implementation

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