Priority Queues and Heaps in Lua

A regular queue serves elements in the order they were added. A priority queue is different: each element carries a priority value, and the queue always serves the element with the highest priority first. Lower numbers often mean higher priority, so a task with priority 1 gets processed before a task with priority 5.

This distinction matters more than it sounds. When a CPU scheduler decides which process runs next, or when an event-driven simulation needs the earliest scheduled event, a priority queue is exactly the right tool. The underlying data structure that makes this efficient is called a binary heap.

What is a Binary Heap?

A binary heap is a complete binary tree stored compactly in an array. “Complete” means every level is filled except possibly the last, and the last level is filled from left to right. This shape guarantees the tree has height ⌊log₂ n⌋, which is why heap operations stay fast.

In a min-heap, every node’s key is less than or equal to the keys of its children. The smallest element always sits at the root. In a max-heap, the largest element is at the root.

The heap lives in a Lua table using 1-indexed positions. Because Lua tables start at index 1 rather than 0, the parent and child formulas are:

parent(i)  = math.floor(i / 2)
left(i)    = 2 * i
right(i)   = 2 * i + 1
```lua

For example, a min-heap with elements `2, 5, 3, 8, 7` looks like this as a tree and as a table:

```lua
        2               Table: { 2, 5, 3, 8, 7 }
       / \              Index:   1  2  3  4  5
      5   3
     / \
    8   7

The root at heap[1] is 2 — the minimum. The children of index 2 (the 5) are at indices 4 and 5, which holds 8 and 7. This mapping falls out of the arithmetic with no pointers needed.

The Core Heap Operations

Two procedures do the heavy lifting: sift up and sift down. Everything else builds on them.

Sift Up — Restoring Order After Insert

When you insert a new element, you place it at the end of the array and compare it with its parent. If it violates the heap property (smaller than its parent in a min-heap), you swap them and continue upward. You stop when the element finds its correct position or reaches the root.

local function heapParent(i)
    return math.floor(i / 2)
end

local function siftUp(heap, idx)
    while idx > 1 do
        local p = heapParent(idx)
        if heap[idx] < heap[p] then
            heap[idx], heap[p] = heap[p], heap[idx]
            idx = p
        else
            break
        end
    end
end
```lua

This costs `O(log n)` in the worst case — at most one swap per level.

### Sift Down — Restoring Order After Extract

When you remove the root, you move the last element to the root and push it down. At each step, you compare it with its two children and swap it with the smaller one (in a min-heap). This continues until the element is smaller than both children or reaches a leaf.

```lua
local function heapLeft(i)
    return 2 * i
end

local function heapRight(i)
    return 2 * i + 1
end

local function siftDown(heap, idx)
    local n = #heap
    while true do
        local smallest = idx
        local l = heapLeft(idx)
        if l <= n and heap[l] < heap[smallest] then
            smallest = l
        end
        local r = heapRight(idx)
        if r <= n and heap[r] < heap[smallest] then
            smallest = r
        end
        if smallest ~= idx then
            heap[idx], heap[smallest] = heap[smallest], heap[idx]
            idx = smallest
        else
            break
        end
    end
end
```lua

Extract-min from `[2, 5, 3, 8, 7]`:
1. Remove root `2`
2. Move last (`7`) to root: `[7, 5, 3, 8]`
3. `7 > 3`, swap with `3`: `[3, 5, 7, 8]`
4. `7` has no children (index `3` has children `6` and `7`, both beyond size `4`). Done.

## Building a Priority Queue in Lua

With `siftUp` and `siftDown` in hand, the priority queue operations are straightforward.

```lua
local PriorityQueue = {}
PriorityQueue.__index = PriorityQueue

function PriorityQueue.new(isMax)
    local less = function(a, b)
        return isMax and (a > b) or (a < b)
    end

    local function heapParent(i)
        return math.floor(i / 2)
    end

    local function siftUp(heap, idx)
        while idx > 1 do
            local p = heapParent(idx)
            if less(heap[p], heap[idx]) then
                heap[idx], heap[p] = heap[p], heap[idx]
                idx = p
            else break end
        end
    end

    local function siftDown(heap, idx)
        local n = #heap
        while true do
            local smallest = idx
            local l = 2 * idx
            if l <= n and less(heap[smallest], heap[l]) then smallest = l end
            local r = 2 * idx + 1
            if r <= n and less(heap[smallest], heap[r]) then smallest = r end
            if smallest ~= idx then
                heap[idx], heap[smallest] = heap[smallest], heap[idx]
                idx = smallest
            else break end
        end
    end

    local function push(value)
        table.insert(self.data, value)
        siftUp(self.data, #self.data)
    end

    local function pop()
        local top = self.data[1]
        local last = table.remove(self.data)
        if #self.data > 0 then
            self.data[1] = last
            siftDown(self.data, 1)
        end
        return top
    end

    local self = setmetatable({ data = {}, isMax = isMax or false }, PriorityQueue)
    self.push = push
    self.pop = pop
    return self
end

function PriorityQueue:peek()
    return self.data[1]
end

function PriorityQueue:size()
    return #self.data
end
```lua

Using it:

```lua
local pq = PriorityQueue.new()
pq:push(3)
pq:push(1)
pq:push(4)
pq:push(1)
pq:push(5)

pq:pop()  --> 1
pq:pop()  --> 1
pq:pop()  --> 3
```lua

The duplicate `1` values are fine — equal priorities resolve in FIFO order among themselves, which matches most real-world scheduling semantics.

## Heapify — Building a Heap in O(n)

Inserting elements one at a time costs `O(n log n)` to build. But you can build a heap from an unsorted array in `O(n)` by calling `siftDown` on each non-leaf node, starting from the last internal node and working backward to the root.

```lua
local function heapify(arr, isMax)
    local less = function(a, b)
        return isMax and (a > b) or (a < b)
    end

    local function siftDown(heap, idx)
        local n = #heap
        while true do
            local smallest = idx
            local l = 2 * idx
            if l <= n and less(heap[smallest], heap[l]) then smallest = l end
            local r = 2 * idx + 1
            if r <= n and less(heap[smallest], heap[r]) then smallest = r end
            if smallest ~= idx then
                heap[idx], heap[smallest] = heap[smallest], heap[idx]
                idx = smallest
            else break end
        end
    end

    local n = #arr
    for i = math.floor(n / 2), 1, -1 do
        siftDown(arr, i)
    end
    return arr
end
```lua

For a max-heap, pass `true` as the second argument. This is the same algorithm that heap sort uses under the hood.

## Task Scheduler Example

Here is a more complete example: a task scheduler where each task is a table with a `name` and a numeric `priority`. Lower numbers mean more urgent.

```lua
local TaskScheduler = {}
TaskScheduler.__index = TaskScheduler

function TaskScheduler.new()
    return setmetatable({ tasks = {} }, TaskScheduler)
end

-- Sift up for tasks ordered by priority
function TaskScheduler:_siftUp(idx)
    while idx > 1 do
        local p = math.floor(idx / 2)
        if self.tasks[idx].priority < self.tasks[p].priority then
            self.tasks[idx], self.tasks[p] = self.tasks[p], self.tasks[idx]
            idx = p
        else break end
    end
end

-- Sift down for tasks ordered by priority
function TaskScheduler:_siftDown(idx)
    local n = #self.tasks
    while true do
        local smallest = idx
        local l = 2 * idx
        if l <= n and self.tasks[l].priority < self.tasks[smallest].priority then
            smallest = l
        end
        local r = 2 * idx + 1
        if r <= n and self.tasks[r].priority < self.tasks[smallest].priority then
            smallest = r
        end
        if smallest ~= idx then
            self.tasks[idx], self.tasks[smallest] = self.tasks[smallest], self.tasks[idx]
            idx = smallest
        else break end
    end
end

function TaskScheduler:add(name, priority)
    table.insert(self.tasks, { name = name, priority = priority })
    self:_siftUp(#self.tasks)
end

function TaskScheduler:next()
    local task = self.tasks[1]
    local last = table.remove(self.tasks)
    if #self.tasks > 0 then
        self.tasks[1] = last
        self:_siftDown(1)
    end
    return task
end

function TaskScheduler:size()
    return #self.tasks
end

-- Demo
local sched = TaskScheduler.new()
sched:add("Crash recovery", 1)
sched:add("Send heartbeat", 5)
sched:add("Log rotation", 3)
sched:add("Memory compaction", 2)

while sched:size() > 0 do
    local t = sched:next()
    print(t.priority, t.name)
end
```lua

Output:

```lua
1   Crash recovery
2   Memory compaction
3   Log rotation
5   Send heartbeat
```lua

The heap always delivers the most urgent task first. Adding a new task costs `O(log n)`, and extracting the next task also costs `O(log n)`. This is significantly faster than scanning an unsorted list for every extraction.

## Event Queue for Simulations

Game engines and simulators often need to process events in chronological order. An event queue backed by a min-heap gives you exactly that: schedule events with timestamps, and the next event to process is always at the root.

```lua
local EventQueue = {}
EventQueue.__index = EventQueue

function EventQueue.new()
    return setmetatable({ events = {} }, EventQueue)
end

function EventQueue:_siftUp(idx)
    while idx > 1 do
        local p = math.floor(idx / 2)
        if self.events[idx].time < self.events[p].time then
            self.events[idx], self.events[p] = self.events[p], self.events[idx]
            idx = p
        else break end
    end
end

function EventQueue:_siftDown(idx)
    local n = #self.events
    while true do
        local smallest = idx
        local l = 2 * idx
        if l <= n and self.events[l].time < self.events[smallest].time then
            smallest = l
        end
        local r = 2 * idx + 1
        if r <= n and self.events[r].time < self.events[smallest].time then
            smallest = r
        end
        if smallest ~= idx then
            self.events[idx], self.events[smallest] = self.events[smallest], self.events[idx]
            idx = smallest
        else break end
    end
end

function EventQueue:schedule(event, time)
    table.insert(self.events, { event = event, time = time })
    self:_siftUp(#self.events)
end

function EventQueue:pop()
    local next = self.events[1]
    local last = table.remove(self.events)
    if #self.events > 0 then
        self.events[1] = last
        self:_siftDown(1)
    end
    return next.event, next.time
end

function EventQueue:peekTime()
    return self.events[1] and self.events[1].time
end

-- Demo: game event simulation
local eq = EventQueue.new()
eq:schedule("Player lands", 1.0)
eq:schedule("Player jumps", 0.5)
eq:schedule("Game over", 3.0)
eq:schedule("Spawn enemy", 2.1)

while #eq.events > 0 do
    local evt, t = eq:pop()
    print(string.format("%.1f: %s", t, evt))
end
```lua

Output:

```lua
0.5: Player jumps
1.0: Player lands
2.1: Spawn enemy
3.0: Game over
```lua

The heap kept events ordered by timestamp without any explicit sorting step. Scheduling is `O(log n)` and each extraction is also `O(log n)`.

## Dijkstra's Algorithm with a Priority Queue

Priority queues are not just for scheduling. In Dijkstra's shortest-path algorithm, the heap stores unvisited nodes keyed by their current known distance. The algorithm repeatedly extracts the node with the smallest distance, then relaxes its neighbors.

```lua
local function dijkstra(graph, start)
    local dist = {}
    dist[start] = 0

    -- Min-heap of { node, dist }
    local pq = PriorityQueue.new()
    pq:push({ node = start, dist = 0 })

    while pq:size() > 0 do
        local entry = pq:pop()
        local u, d = entry.node, entry.dist

        -- Skip stale entries
        if d > (dist[u] or math.huge) then
            goto continue
        end

        for _, edge in ipairs(graph[u] or {}) do
            local v = edge.to
            local w = edge.weight
            if (dist[v] or math.huge) > d + w then
                dist[v] = d + w
                pq:push({ node = v, dist = dist[v] })
            end
        end

        ::continue::
    end

    return dist
end

A naive implementation like this inserts a new entry every time a shorter path is found, which means the heap can contain multiple entries for the same node. Stale entries get skipped on extraction. For better performance with many distance updates, a position map (a dictionary from node to its current heap index) enables true decrease-key operations in O(log n) instead of inserting duplicates.

Complexity Summary

Operation	Time
Insert / push	O(log n)
Extract-min / pop	O(log n)
Peek	O(1)
Decrease-key (with position map)	O(log n)
Build heap (heapify)	O(n)
Space	O(n)

The binary heap wins over alternatives like a sorted array (slow insert) or an unsorted array (slow extract) because it keeps both operations at O(log n). Compared to a balanced BST, the heap has a smaller constant factor since it avoids the overhead of maintaining tree balance.

See Also

• /tutorials/ds-stacks-and-queues — The queue fundamentals this article builds on
• /tutorials/functions-in-lua — Closures and first-class functions that make the heap implementation clean
• /guides/lua-metatables — Metatables for wrapping the heap in a clean object-oriented API