xmake-docs/docs/api/scripts/extension-modules/core/base/heap.md

heap

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

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

heap.valueheap

• Create a value heap

Function Prototype

::: tip 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

::: tip 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 TIP The value cannot be nil. :::

heap:pop

• Pop a value from the heap

Function Prototype

::: tip 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

::: tip 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

::: tip 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 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

::: tip 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 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 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 :::