Class: PriorityQueue
- Inherits:
-
Object
- Object
- PriorityQueue
- Defined in:
- lib/priority_queue.rb
Overview
Priority Queue Reference: github.com/python/cpython/blob/main/Lib/heapq.py
Instance Attribute Summary collapse
-
#heap ⇒ Object
(also: #to_a)
readonly
Returns the value of attribute heap.
Class Method Summary collapse
Instance Method Summary collapse
-
#empty? ⇒ Boolean
Returns true if the heap is empty.
-
#get ⇒ Object
(also: #top, #first)
Get the element with the highest priority.
-
#initialize(array = [], &comp) ⇒ PriorityQueue
constructor
By default, the priority queue returns the maximum element first.
-
#pop ⇒ Object
Pop the element with the highest priority.
-
#push(item) ⇒ Object
(also: #<<, #append)
Push new element to the heap.
- #size ⇒ Object
- #to_s ⇒ Object
Constructor Details
#initialize(array = [], &comp) ⇒ PriorityQueue
By default, the priority queue returns the maximum element first. If a block is given, the priority between the elements is determined with it. For example, the following block is given, the priority queue returns the minimum element first. ‘PriorityQueue.new { |x, y| x < y }`
A heap is an array for which a <= a and a <= a for all k, counting elements from 0.
10 11 12 13 14 |
# File 'lib/priority_queue.rb', line 10 def initialize(array = [], &comp) @heap = array @comp = comp || proc { |x, y| x > y } heapify end |
Instance Attribute Details
#heap ⇒ Object (readonly) Also known as: to_a
Returns the value of attribute heap.
28 29 30 |
# File 'lib/priority_queue.rb', line 28 def heap @heap end |
Class Method Details
.[](*array, &comp) ⇒ Object
24 25 26 |
# File 'lib/priority_queue.rb', line 24 def self.[](*array, &comp) new(array, &comp) end |
.max(array) ⇒ Object
16 17 18 |
# File 'lib/priority_queue.rb', line 16 def self.max(array) new(array) end |
.min(array) ⇒ Object
20 21 22 |
# File 'lib/priority_queue.rb', line 20 def self.min(array) new(array){ |x, y| x < y } end |
Instance Method Details
#empty? ⇒ Boolean
Returns true if the heap is empty.
60 61 62 |
# File 'lib/priority_queue.rb', line 60 def empty? @heap.empty? end |
#get ⇒ Object Also known as: top, first
Get the element with the highest priority.
52 53 54 |
# File 'lib/priority_queue.rb', line 52 def get @heap[0] end |
#pop ⇒ Object
Pop the element with the highest priority.
41 42 43 44 45 46 47 48 49 |
# File 'lib/priority_queue.rb', line 41 def pop latest = @heap.pop return latest if empty? ret_item = heap[0] heap[0] = latest shift_up(0) ret_item end |
#push(item) ⇒ Object Also known as: <<, append
Push new element to the heap.
32 33 34 35 |
# File 'lib/priority_queue.rb', line 32 def push(item) shift_down(0, @heap.push(item).size - 1) self end |
#size ⇒ Object
64 65 66 |
# File 'lib/priority_queue.rb', line 64 def size @heap.size end |
#to_s ⇒ Object
68 69 70 |
# File 'lib/priority_queue.rb', line 68 def to_s "<#{self.class}: @heap:(#{heap.join(', ')}), @comp:<#{@comp.class} #{@comp.source_location.join(':')}>>" end |