`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 initialize`

Initializes the heap.

Implementation

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

`def peek`

Signature

returns　Object | Nil: the smallest element in the heap without removing it, or nil if the heap is empty.

Implementation

def peek
	@contents[0]
end

`def size`

Signature

returns　Integer: the number of elements in the heap.

Implementation

def size
	@contents.size
end

`def pop`

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

Signature

returns　Object | Nil: The smallest element in the heap, or nil if the heap is empty.

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)`

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

Signature

parameter　element　Object: The element to add to the heap.

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