How to resolve the algorithm Priority queue step by step in the Lua programming language

Published on 12 May 2024 09:40 PM
#Lua

How to resolve the algorithm Priority queue step by step in the Lua programming language

Table of Contents

Problem Statement

A priority queue is somewhat similar to a queue, with an important distinction: each item is added to a priority queue with a priority level, and will be later removed from the queue with the highest priority element first. That is, the items are (conceptually) stored in the queue in priority order instead of in insertion order.

Create a priority queue.   The queue must support at least two operations:

Optionally, other operations may be defined, such as peeking (find what current top priority/top element is), merging (combining two priority queues into one), etc.

To test your implementation, insert a number of elements into the queue, each with some random priority. Then dequeue them sequentially; now the elements should be sorted by priority. You can use the following task/priority items as input data:

The implementation should try to be efficient.   A typical implementation has   O(log n)   insertion and extraction time,   where   n   is the number of items in the queue.
You may choose to impose certain limits such as small range of allowed priority levels, limited capacity, etc.   If so, discuss the reasons behind it.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Priority queue step by step in the Lua programming language

Source code in the lua programming language

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


-- Use socket.gettime() for benchmark measurements
-- since it has millisecond precision on most systems
local socket = require("socket")

n = 10000000 -- number of tasks added (10^7)
m = 1000     -- number different priorities

local pq = PriorityQueue()

print(string.format("Adding %d tasks with random priority 1-%d ...", n, m))
start = socket.gettime()

for i = 1, n do
    pq:put(math.random(m), i)
end

print(string.format("Elapsed: %.3f ms.", (socket.gettime() - start) * 1000))

print("Retrieving all tasks in order...")
start = socket.gettime()

local pp = 0
local pv = 0

for i = 1, n do
    local p, task = pq:pop()

    -- check that tasks are popped in ascending priority
    assert(p >= pp)

    if pp == p then
        -- check that tasks within one priority maintain the insertion order
        assert(task > pt)
    end

    pp = p
    pt = task
end

print(string.format("Elapsed: %.3f ms.", (socket.gettime() - start) * 1000))

You may also check:How to resolve the algorithm Copy a string step by step in the PHP programming language
You may also check:How to resolve the algorithm Factors of an integer step by step in the Python programming language
You may also check:How to resolve the algorithm Pseudo-random numbers/PCG32 step by step in the Haskell programming language
You may also check:How to resolve the algorithm Search a list step by step in the Julia programming language
You may also check:How to resolve the algorithm Jacobi symbol step by step in the Raku programming language