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
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
endIt's recommended to put it all together in one Lua module file.
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
endThis 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