class PriorityQueue::MinHeap(T)
- PriorityQueue::MinHeap(T)
- Reference
- Object
Overview
Implements a minimum-first PriorityQueue using an array-based heap.
Direct Known Subclasses
Defined in:
priorityqueue.crConstructors
-
.new(data : Enumerable(T))
Constructs a
PriorityQueuefrom an initial set of data, in linear time. -
.new
Constructs an empty
PriorityQueue.
Instance Method Summary
-
#clear
Empties the priority queue, discarding any data it contained.
-
#empty?
Returns a boolean indicating whether the queue is empty or not.
-
#peek
Inspects the element at the head of the queue without removing it.
-
#pop
Removes and returns the element at the head of the queue.
-
#push(element : T)
Pushes a single element onto the priority queue.
-
#replace_first(element : T)
Replaces the current first element with the provided element, then reorders the elements as needed to restore the heap property.
-
#size
Returns the number of elements currently stored in the queue.
Constructor Detail
Constructs a PriorityQueue from an initial set of data, in linear time.
The data can be provided as any Enumerable collection, such as an Array.
Instance Method Detail
Empties the priority queue, discarding any data it contained.
Returns self so that operations can be chained.
Inspects the element at the head of the queue without removing it.
Returns the value of the first item in the queue, or nil if the
queue is empty.
Removes and returns the element at the head of the queue.
Returns the value of the first item in the queue, or nil if the
queue is empty.
Pushes a single element onto the priority queue.
Returns self so that operations can be chained.
Replaces the current first element with the provided element, then reorders the elements as needed to restore the heap property.
This would usually be done after a #peek to improve efficiency.
If you frequently do a #push immediately after performing a #pop
this method eliminates the bubble-up operation performed by #pop,
cutting the number of traversals of the heap in half.
Returns self so that operations can be chained.