`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 empty?`

Signature

returns　Boolean: true if the heap is empty, false otherwise.

Implementation

def empty?
	@contents.empty?
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 concat(elements)`

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

Signature

parameter　elements　Array: The elements to add to the heap.
returns　self: Returns self for method chaining.

Implementation

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

`def clear!`

Empties out the heap, discarding all elements

Implementation

def clear!
	@contents = []
end

`def delete(element)`

Remove a specific element from the heap.

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

Signature

parameter　element　Object: The element to remove.
returns　Object | Nil: The removed element, or nil if not found.

Implementation

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

`def delete_if`

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.

Signature

returns　Integer: The number of elements removed

Implementation

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

`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? {|index| @contents[index] >= @contents[(index - 1) / 2]}
end

`def heapify!`

Rebuild the heap property from an arbitrary array in O(n) time. Uses bottom-up heapify algorithm starting from the last non-leaf node.

Implementation

def heapify!
	return if @contents.size <= 1
	
	# Start from the last non-leaf node and work backwards to root:
	last_non_leaf_index = (@contents.size / 2) - 1
	last_non_leaf_index.downto(0) do |index|
		bubble_down(index)
	end
	
	# validate!
end