class AcLibraryRb::HeapQueue
Priority Queue Reference: github.com/python/cpython/blob/master/Lib/heapq.py
Attributes
heap[R]
Public Class Methods
new(array = [], &comp)
click to toggle source
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.
# File lib_lock/ac-library-rb/priority_queue.rb, line 11 def initialize(array = [], &comp) @heap = array @comp = comp || proc { |x, y| x > y } heapify end
Public Instance Methods
empty?()
click to toggle source
Returns true if the heap is empty.
# File lib_lock/ac-library-rb/priority_queue.rb, line 46 def empty? @heap.empty? end
get()
click to toggle source
Get the element with the highest priority.
# File lib_lock/ac-library-rb/priority_queue.rb, line 39 def get @heap[0] end
Also aliased as: top
pop()
click to toggle source
Pop the element with the highest priority.
# File lib_lock/ac-library-rb/priority_queue.rb, line 28 def pop latest = @heap.pop return latest if empty? ret_item = heap[0] heap[0] = latest shift_up(0) ret_item end
push(item)
click to toggle source
Push new element to the heap.
# File lib_lock/ac-library-rb/priority_queue.rb, line 20 def push(item) shift_down(0, @heap.push(item).size - 1) end
Private Instance Methods
heapify()
click to toggle source
# File lib_lock/ac-library-rb/priority_queue.rb, line 52 def heapify (@heap.size / 2 - 1).downto(0) { |i| shift_up(i) } end
shift_down(star_pos, pos)
click to toggle source
# File lib_lock/ac-library-rb/priority_queue.rb, line 76 def shift_down(star_pos, pos) new_item = @heap[pos] while pos > star_pos parent_pos = (pos - 1) >> 1 parent = @heap[parent_pos] break if @comp.call(parent, new_item) @heap[pos] = parent pos = parent_pos end @heap[pos] = new_item end
shift_up(pos)
click to toggle source
# File lib_lock/ac-library-rb/priority_queue.rb, line 56 def shift_up(pos) end_pos = @heap.size start_pos = pos new_item = @heap[pos] left_child_pos = 2 * pos + 1 while left_child_pos < end_pos right_child_pos = left_child_pos + 1 if right_child_pos < end_pos && @comp.call(@heap[right_child_pos], @heap[left_child_pos]) left_child_pos = right_child_pos end # Move the higher priority child up. @heap[pos] = @heap[left_child_pos] pos = left_child_pos left_child_pos = 2 * pos + 1 end @heap[pos] = new_item shift_down(start_pos, pos) end