class Concurrent::MutexPriorityQueue

@see docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html<br><br>@see algs4.cs.princeton.edu/24pq/MaxPQ.java.html<br>@see algs4.cs.princeton.edu/24pq/index.php#2.6<br><br>@see ruby-doc.org/stdlib-2.0.0/libdoc/thread/rdoc/Queue.html<br>@see en.wikipedia.org/wiki/Priority_queue<br><br>@note This implementation is not thread safe and performs no blocking.
When running under all other interpreters it extends ‘MutexPriorityQueue`.
When running under JRuby the class `PriorityQueue` extends `JavaPriorityQueue`.
library `java.util.PriorityQueue`.
The JRuby native implementation is a thin wrapper around the standard
and Kevin Wayne.
stored in an array. The algorithm is based on the work of Robert Sedgewick
The pure Ruby implementation, `MutexPriorityQueue` uses a heap algorithm
The API is based on the `Queue` class from the Ruby standard library.
set on construction.
from highest to lowest, but a lowest-to-highest sort order can be
with the “highest” priority is removed. By default the sort order is
at a position relative to their priority. On removal the element
comparison (spaceship) operator `<=>`. Items are added to the queue
A queue collection in which the elements are sorted based on their
@!macro [attach] priority_queue

def self.from_list(list, opts = {})

Returns:
  • (PriorityQueue) - the newly created and populated queue

Parameters:
  • opts (Hash) -- the options for creating the queue
  • list (Enumerable) -- the list to build the queue from 
def self.from_list(list, opts = {})
  queue = new(opts)
  list.each{|item| queue << item }
  queue
end

def clear

Removes all of the elements from this priority queue.

@!macro [attach] priority_queue_method_clear 
def clear
  @queue = [nil]
  @length = 0
  true
end

def delete(item)

Returns:
  • (Object) - true if the item is found else false

Parameters:
  • item (Object) -- the item to be removed from the queue 
def delete(item)
  original_length = @length
  k = 1
  while k <= @length
    if @queue[k] == item
      swap(k, @length)
      @length -= 1
      sink(k)
      @queue.pop
    else
      k += 1
    end
  end
  @length != original_length
end

def empty?

Returns:
  • (Boolean) - true if there are no items in the queue else false 
def empty?
  size == 0
end

def include?(item)

Returns:
  • (Boolean) - true if the item is found else false

Parameters:
  • item (Object) -- the item to search for 
def include?(item)
  @queue.include?(item)
end

def initialize(opts = {})

Options Hash: (**opts)
  • :order (Symbol) -- dictates the order in which items are

Parameters:
  • opts (Hash) -- the options for creating the queue 
def initialize(opts = {})
  order = opts.fetch(:order, :max)
  @comparator = [:min, :low].include?(order) ? -1 : 1
  clear
end

def length

Returns:
  • (Fixnum) - the number of items in the queue 
def length
  @length
end

def ordered?(x, y)

Returns:
  • (Boolean) - true if the two elements are in the correct priority order

Parameters:
  • y (Integer) -- the second index from which to retrieve a comparable value
  • x (Integer) -- the first index from which to retrieve a comparable value 
def ordered?(x, y)
  (@queue[x] <=> @queue[y]) == @comparator
end

def peek

Returns:
  • (Object) - the head of the queue or `nil` when empty 
def peek
  @queue[1]
end

def pop

Returns:
  • (Object) - the head of the queue or `nil` when empty 
def pop
  max = @queue[1]
  swap(1, @length)
  @length -= 1
  sink(1)
  @queue.pop
  max
end

def push(item)

Parameters:
  • item (Object) -- the item to insert onto the queue 
def push(item)
  @length += 1
  @queue << item
  swim(@length)
  true
end

def sink(k)

Parameters:
  • k (Integer) -- the index at which to start the percolation 
def sink(k)
  while (j = (2 * k)) <= @length do
    j += 1 if j < @length && ! ordered?(j, j+1)
    break if ordered?(k, j)
    swap(k, j)
    k = j
  end
end

def swap(x, y)

Parameters:
  • y (Integer) -- the second index to swap
  • x (Integer) -- the first index to swap 
def swap(x, y)
  temp = @queue[x]
  @queue[x] = @queue[y]
  @queue[y] = temp
end

def swim(k)

Parameters:
  • k (Integer) -- the index at which to start the percolation 
def swim(k)
  while k > 1 && ! ordered?(k/2, k) do
    swap(k, k/2)
    k = k/2
  end
end