This is a data structure tutorial. I was bored and I wanted to clear my mind so I created this. If you don’t understand that’s fine too. You can check out the cool stuff section and my game place.
Have you seen my resource on a Stack? If you have, then the concept is similar. This tutorial will be much shorter as I try to squeeze in the valuable info.
Queue
A queue is a linear access data structure that can be used to store data employing the principle of FIFO (First in First Out). In a queue, objects are added to the back and removed from the front (Opposite of a stack).
Priority Queue
A priority queue is a data structure that uses a min-heap to determine the highest priority to be removed. “In a priority queue, an element with high priority is served before an element with low priority”. 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.
Implementation
In Lua, the creation of Queues can be created much more easily. A double queue is created in the Lua programming book. http://www.lua.org/pil/11.4.html.
Lua programming book implementation
List = {}
function List.new ()
return {first = 0, last = -1}
end
function List.pushleft (list, value)
local first = list.first - 1
list.first = first
list[first] = value
end
function List.pushright (list, value)
local last = list.last + 1
list.last = last
list[last] = value
end
function List.popleft (list)
local first = list.first
if first > list.last then error("list is empty") end
local value = list[first]
list[first] = nil -- to allow garbage collection
list.first = first + 1
return value
end
function List.popright (list)
local last = list.last
if list.first > last then error("list is empty") end
local value = list[last]
list[last] = nil -- to allow garbage collection
list.last = last - 1
return value
end
In this example, it is shown as a double queue because of the change from both front and back.
Additionally, the following implementation from the Lua Game Development Cookbook shows a similar approach but in a different way.
Lua Game Development Cookbook Implementation
local function queue()
local out = {}
local first, last = 0, -1
out.push = function(item)
last = last + 1
out[last] = item
end
out.pop = function()
if first <= last then
local value = out[first]
out[first] = nil
first = first + 1
return value
end
end
out.iterator = function()
return function()
return out.pop()
end
end
setmetatable(out, {
__len = function()
return (last-first+1)
end,
})
return out
end
It can then be used:
local q1 = queue()
-- Place a few elements into queue
for _, element in ipairs {'Lorem','ipsum','dolor','sit','amet'} do
q1.push(element)
end
-- You can use iterator to process all elements in single for loop
for element in q1.iterator() do
-- each queue element will be printed onto screen
print(element)
end
Both of these implementations are constant time: O(1).
Now that you have seen the basic Queue in Lua, let’s look at priority queues.
Priority queues can help you order execution based on the need of each. A real-life example could be seen like this:
A hospital has a waiting list with patients coming in every minute. In a store, the priority would go to the first person who entered the line. However, a hospital puts the priority on those who are most threatened. This system is common in real life but can be represented as a priority queue.
Better Example
1 person
2 people
3 people
The first 2 are treated
An injured person arrives!
2 people
notice that the injured person is moved to the front instead of the back because his priority is higher than the other
A normal tree priority queue....
In most languages other than Lua, priority queues can also be created using search trees. While Lua can create using trees, there is no reason to when there are tables. Please go to the tree data structure post for more information!
How does a priority queue determine priority? Priority Queue is built in a balanced tree fashion where the parent will have two children and the parent will always have higher priority than the child.
While searching for an image, I found this one. Let’s look at this first. The seven at position 6 is the number we are adding to the priority queue. Just like in a normal queue, we put it in the last position but we are not done. We need to check if 7 is greater than its parent: 5. In this case, it is so we switch positions of 5 and 7 to form: 
.
Now that we have switched the two, we now continue looking at the next parent: 9. Since 7 isn’t bigger than 9, we do not do anything. This is the new order of the queue: 9,3,7,1,4,2,5.
Now lets see a binary heap implementation
Summary
PriorityQueue = {
__index = {
put = function(self, p, v)
local q = self[p]
if not q then
q = {first = 1, last = 0}
self[p] = q
end
q.last = q.last + 1
q[q.last] = v
end,
pop = function(self)
for p, q in pairs(self) do
if q.first <= q.last then
local v = q[q.first]
q[q.first] = nil
q.first = q.first + 1
return p, v
else
self[p] = nil
end
end
end
},
__call = function(cls)
return setmetatable({}, cls)
end
}
setmetatable(PriorityQueue, PriorityQueue)
-- Usage:
pq = PriorityQueue()
tasks = {
{3, 'Clear drains'},
{4, 'Feed cat'},
{5, 'Make tea'},
{1, 'Solve RC tasks'},
{2, 'Tax return'}
}
for _, task in ipairs(tasks) do
print(string.format("Putting: %d - %s", unpack(task)))
pq:put(unpack(task))
end
for prio, task in pq.pop, pq do
print(string.format("Popped: %d - %s", prio, task))
end
cool stuff to use with this
Lets check out a few usages of priority queues. First, lets look at Huffman’s compression algorithm.
Huffman’s compression algorithm is great for compression (the name says it). Huffman coding is a lossless data compression algorithm. How it works is it takes all the unique characters from the input and sorts them by frequency. Each character is given a code based on the frequency. The character with the most frequency will have the shortest code.
Lua Code
Thanks to Rosetta Code 
local build_freqtable = function (data)
local freq = { }
for i = 1, #data do
local cur = string.sub (data, i, i)
local count = freq [cur] or 0
freq [cur] = count + 1
end
local nodes = { }
for w, f in next, freq do
nodes [#nodes + 1] = { word = w, freq = f }
end
table.sort (nodes, function (a, b) return a.freq > b.freq end) --- reverse order!
return nodes
end
local build_hufftree = function (nodes)
while true do
local n = #nodes
local left = nodes [n]
nodes [n] = nil
local right = nodes [n - 1]
nodes [n - 1] = nil
local new = { freq = left.freq + right.freq, left = left, right = right }
if n == 2 then return new end
--- insert new node at correct priority
local prio = 1
while prio < #nodes and nodes [prio].freq > new.freq do
prio = prio + 1
end
table.insert (nodes, prio, new)
end
end
local print_huffcodes do
local rec_build_huffcodes
rec_build_huffcodes = function (node, bits, acc)
if node.word == nil then
rec_build_huffcodes (node.left, bits .. "0", acc)
rec_build_huffcodes (node.right, bits .. "1", acc)
return acc
else --- leaf
acc [#acc + 1] = { node.freq, node.word, bits }
end
return acc
end
print_huffcodes = function (root)
local codes = rec_build_huffcodes (root, "", { })
table.sort (codes, function (a, b) return a [1] < b [1] end)
print ("frequency\tword\thuffman code")
for i = 1, #codes do
print (string.format ("%9d\t‘%s’\t“%s”", table.unpack (codes [i])))
end
end
end
local huffcode = function (data)
local nodes = build_freqtable (data)
local huff = build_hufftree (nodes)
print_huffcodes (huff)
return 0
end
return huffcode "this is an example for huffman encoding"
The question is: did this use priority queues?
The compression can be used in string data for databases or just to compact to smaller sizes. One way I can see this is with a recording system that has a code to play back any time.
A* Pathfinding
to be continued
To sum it all up, priority queues are a data structure used outside of roblox commonly. While in roblox, there really isn’t a clear reason but that doesn’t mean it’s useless. I hope this gives you more info on priority queues outside of roblox and in.