Making a prioritized queue

A prioritized queue or simple priority queue extends basic queue with the entry sorting feature. Upon entry insertion, you can set what will be the priority of the entry. This data structure is often used in job queuing where the most important (highest priority) jobs must be processed before the jobs with lower priority. Priority queues are often used in artificial intelligence as well.

This version of the prioritized queue allows you to obtain entries with minimal or maximal priority at constant time. Element priority can be updated. However, priority queue insertion, update, and removal might use linear time complexity in worst case scenarios.

There are two rules that should be noted:

• Each entry of this queue should be unique
• The order of retrieving elements with the same priority is not defined

Getting ready

This recipe will use the following shortcuts:

local ti = table.insert
local tr = table.remove

-- removes element from table by its value
local tr2 = function(t, v)
  for i=1,#t do
    if t[i]==v then
      tr(t, i)
      break
    end
  end
end

It's recommended to put it all together in one Lua module file.

How to do it…

The priority queue can be defined as in the following code:

return function pqueue()
  -- interface table
  local t = {}

  -- a set of elements
  local set = {}
  -- a set of priority bags with a elements
  local r_set = {}
  -- sorted list of priorities
  local keys = {}

  -- add element into storage, set its priority and sort keys
  --  k - element
  --  v - priority
  local function addKV(k, v)
    set[k] = v
    -- create a new list for this priority
    if not r_set[v] then
      ti(keys, v)
      table.sort(keys)
      local k0 = {k}
      r_set[v] = k0
      setmetatable(k0, {
        __mode = 'v'
      })
    -- add element into list for this priority
    else
      ti(r_set[v], k)
    end
  end

  -- remove element from storage and sort keys
  local remove = function(k)
    local v = set[k]
    local prioritySet = r_set[v]
    tr2(prioritySet, k)
    if #prioritySet < 1 then
      tr2(keys, v)
      r_set[v] = nil
      table.sort(keys)
      set[k] = nil
    end
  end; t.remove = remove

  -- returns an element with the lowest priority
  t.min = function()
    local priority = keys[1]
    if priority then
      return r_set[priority][1] or {}
    else
      return {}
    end
  end

  -- returns an element with the highest priority
  t.max = function()
    local priority = keys[#keys]
    if priority then
      return r_set[priority][1] or {}
    else
      return {}
    end
  end

  -- is this queue empty?
  t.empty = function()
    return #keys < 1
  end
  -- simple element iterator, retrieves elements with
  -- the highest priority first
  t.iterate = function()
    return function()
      if not t.empty() then
        local element = t.max()
        t.remove(element)
        return element
      end
    end
  end
  -- setup pqueue behavior
  setmetatable(t, {
    __index = set,
    __newindex = function(t, k, v)
      if not set[k] then
        -- new item
        addKV(k, v)
      else
        -- existing item
        remove(k)
        addKV(k, v)
      end
    end,
  })
  return t
end

How it works…

This priority queue algorithm uses three tables: set, r_set, and keys. These tables help to organize elements into so-called priority bags. The first one, set contains elements paired with their priorities. It's also used when you try to obtain element priority from the queue. The second one, r_set contains priority bags. Each bag represents a priority level. The last one keys contains a sorted list of priorities, which is used in the extraction of elements from a minimal or maximal priority bag.

Each element can be inserted in a way similar to the Lua table with the exception that the inserted element is used as a key and priority is stored as a value:

priority_queue[element] = priority

This form of access can be used to update element priority. Elements with minimal or maximal priority can be extracted using the min or max function respectively;

local min_element = priority_queue.min()
local max_element = priority_queue.max()

Note that elements remain in the priority queue until you delete them with the remove function;

priority_queue.remove(element)

Priority queue can be queried with the empty function that returns true if there's no element in the queue;

priority_queue.empty()

You can use the iterator function in for loop to process all queue elements sorted by their priority:

for element in priority_queue.iterator() do
  -- do something with this element
end