heap

The heap module provides priority queue data structures implemented as binary heaps. This is an extension module of xmake.

TIP

To use this module, you need to import it first: import("core.base.heap")

heap.valueheap

• Create a value heap

Function Prototype

API

heap.valueheap(options: <table>)

Parameter Description

Parameter	Description
options	Optional. Lua table with options

Parameters in options:

• cmp - Optional comparison function. Should return true if the first argument has higher priority than the second

Usage

Creates a new value heap using a Lua table. The heap is a min-heap by default, but can be customized with a comparison function.

-- Create a min-heap (default)
local h = heap.valueheap()

-- Create a max-heap
local h = heap.valueheap{
    cmp = function(a, b)
        return a > b
    end
}

-- Create a priority queue with custom objects
local h = heap.valueheap{
    cmp = function(a, b)
        return a.priority < b.priority
    end
}

Initialize with existing values:

-- Create heap with initial values
local h = heap.valueheap{1, 5, 3, 7, 2}

heap:push

• Push a value onto the heap

Function Prototype

API

heap:push(value: <any>)

Parameter Description

Parameter	Description
value	Required. Value to push onto the heap

Usage

Adds a value to the heap and maintains the heap property. The value will be placed in the correct position according to the comparison function.

local h = heap.valueheap()
h:push(10)
h:push(5)
h:push(20)
h:push(3)

print(h:peek())  -- Output: 3 (smallest value)

Push custom objects:

local h = heap.valueheap{
    cmp = function(a, b)
        return a.priority < b.priority
    end
}

h:push{priority = 20, data = 'low'}
h:push{priority = 10, data = 'high'}
h:push{priority = 15, data = 'medium'}

print(h:peek().data)  -- Output: high (priority 10)

TIP

The value cannot be nil.

heap:pop

• Pop a value from the heap

Function Prototype

API

heap:pop(index: <number>)

Parameter Description

Parameter	Description
index	Optional. The position to pop from (1-based). Defaults to 1 (top of heap)

Usage

Removes and returns a value from the heap. If no index is provided, removes the top element (highest priority). After removal, the heap property is maintained.

local h = heap.valueheap()
h:push(10)
h:push(5)
h:push(20)

local v1 = h:pop()  -- Returns 5 (smallest)
local v2 = h:pop()  -- Returns 10
local v3 = h:pop()  -- Returns 20

Pop with custom priority:

local h = heap.valueheap{
    cmp = function(a, b)
        return a.priority < b.priority
    end
}

h:push{priority = 20, data = 'bar'}
h:push{priority = 10, data = 'foo'}

local item = h:pop()
print(item.priority)  -- Output: 10
print(item.data)      -- Output: foo

heap:peek

• Peek at a value without removing it

Function Prototype

API

heap:peek(index: <number>)

Parameter Description

Parameter	Description
index	Optional. The position to peek at (1-based). Defaults to 1 (top of heap)

Usage

Returns a value from the heap without removing it. If no index is provided, returns the top element (highest priority).

local h = heap.valueheap()
h:push(10)
h:push(5)
h:push(20)

print(h:peek())  -- Output: 5 (smallest)
print(h:peek())  -- Output: 5 (still there)

local v = h:pop()
print(h:peek())  -- Output: 10 (next smallest)

Check next task without processing:

local h = heap.valueheap{
    cmp = function(a, b)
        return a.priority < b.priority
    end
}

h:push{priority = 10, task = 'urgent'}
h:push{priority = 20, task = 'normal'}

if h:peek().priority < 15 then
    print("Processing urgent task")
    local task = h:pop()
end

heap:replace

• Replace a value at a given index

Function Prototype

API

heap:replace(index: <number>, value: <any>)

Parameter Description

Parameter	Description
index	Required. The position to replace (1-based)
value	Required. The new value

Usage

Replaces the value at the specified index with a new value and rebalances the heap to maintain the heap property.

local h = heap.valueheap()
h:push(10)
h:push(5)
h:push(20)

-- Replace the top element
h:replace(1, 15)

print(h:pop())  -- Output: 10
print(h:pop())  -- Output: 15
print(h:pop())  -- Output: 20

Update priority in a priority queue:

local h = heap.valueheap{
    cmp = function(a, b)
        return a.priority < b.priority
    end
}

h:push{priority = 10, id = 1}
h:push{priority = 20, id = 2}
h:push{priority = 15, id = 3}

-- Update priority of element at index 2
h:replace(2, {priority = 5, id = 2})

print(h:pop().id)  -- Output: 2 (now has highest priority)

TIP

Use replace when you need to update an element's priority without removing and re-adding it, which is more efficient.

heap.length

• Get the number of elements in the heap

Function Prototype

API

heap:length()

Parameter Description

No parameters required for this function.

Usage

Returns the current number of elements in the heap. This is a function, not a method.

local h = heap.valueheap()
h:push(10)
h:push(5)
h:push(20)

print(h.length())  -- Output: 3

h:pop()
print(h.length())  -- Output: 2

Check if heap is empty:

local h = heap.valueheap()

if h.length() == 0 then
    print("Heap is empty")
end

h:push(10)

if h.length() > 0 then
    print("Heap has", h.length(), "elements")
end

Process all elements:

local h = heap.valueheap()
h:push(10)
h:push(5)
h:push(20)

while h.length() > 0 do
    local v = h:pop()
    print(v)  -- Output: 5, 10, 20
end

TIP

The heap module implements a binary heap (priority queue) data structure. By default, it's a min-heap where the smallest element has the highest priority. You can customize the comparison function to create max-heaps or heaps based on custom priority criteria. Heap operations (push, pop, peek, replace) all have O(log n) time complexity.

WARNING

• Pushed values cannot be nil
• Index is 1-based (Lua convention)
• Calling pop() on an empty heap will cause an error
• length() is a function, not a property, so use h.length() not h.length