heap

heap 模块提供了使用二叉堆实现的优先队列数据结构。这是 xmake 的扩展模块。

提示

使用此模块需要先导入：import("core.base.heap")

heap.valueheap

• 创建值堆

import("core.base.heap")

local h = heap.valueheap(options)

使用 Lua 表创建一个新的值堆。默认情况下堆是最小堆，但可以使用比较函数进行自定义。

options 中的参数：

• cmp - 可选的比较函数。如果第一个参数的优先级高于第二个参数，应返回 true

-- 创建最小堆（默认）
local h = heap.valueheap()

-- 创建最大堆
local h = heap.valueheap{
    cmp = function(a, b)
        return a > b
    end
}

-- 创建自定义对象的优先队列
local h = heap.valueheap{
    cmp = function(a, b)
        return a.priority < b.priority
    end
}

使用现有值初始化：

-- 使用初始值创建堆
local h = heap.valueheap{1, 5, 3, 7, 2}

heap:push

• 向堆中推入一个值

heap:push(value)

向堆中添加一个值并维护堆属性。该值将根据比较函数放置在正确的位置。

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

print(h:peek())  -- 输出: 3 (最小值)

推入自定义对象：

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)  -- 输出: high (优先级 10)

提示

值不能为 nil。

heap:pop

• 从堆中弹出一个值

local value = heap:pop(index)

从堆中移除并返回一个值。如果未提供索引，则移除顶部元素（最高优先级）。移除后，堆属性将得到维护。

参数：

• index - 可选。要弹出的位置（从 1 开始）。默认为 1（堆顶）

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

local v1 = h:pop()  -- 返回 5 (最小)
local v2 = h:pop()  -- 返回 10
local v3 = h:pop()  -- 返回 20

使用自定义优先级弹出：

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)  -- 输出: 10
print(item.data)      -- 输出: foo

heap:peek

• 查看值而不移除它

local value = heap:peek(index)

从堆中返回一个值而不移除它。如果未提供索引，则返回顶部元素（最高优先级）。

参数：

• index - 可选。要查看的位置（从 1 开始）。默认为 1（堆顶）

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

print(h:peek())  -- 输出: 5 (最小)
print(h:peek())  -- 输出: 5 (仍然存在)

local v = h:pop()
print(h:peek())  -- 输出: 10 (下一个最小)

检查下一个任务而不处理：

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("处理紧急任务")
    local task = h:pop()
end

heap:replace

• 替换给定索引处的值

heap:replace(index, value)

将指定索引处的值替换为新值，并重新平衡堆以维护堆属性。

参数：

• index - 必需。要替换的位置（从 1 开始）
• value - 必需。新值

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

-- 替换顶部元素
h:replace(1, 15)

print(h:pop())  -- 输出: 10
print(h:pop())  -- 输出: 15
print(h:pop())  -- 输出: 20

在优先队列中更新优先级：

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}

-- 更新索引 2 处元素的优先级
h:replace(2, {priority = 5, id = 2})

print(h:pop().id)  -- 输出: 2 (现在具有最高优先级)

提示

当需要更新元素的优先级而不删除和重新添加它时，使用 replace，这样更高效。

heap.length

• 获取堆中的元素数量

local count = heap.length()

返回堆中当前的元素数量。这是一个函数，不是方法。

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

print(h.length())  -- 输出: 3

h:pop()
print(h.length())  -- 输出: 2

检查堆是否为空：

local h = heap.valueheap()

if h.length() == 0 then
    print("堆为空")
end

h:push(10)

if h.length() > 0 then
    print("堆有", h.length(), "个元素")
end

处理所有元素：

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

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

提示

heap 模块实现了二叉堆（优先队列）数据结构。默认情况下，它是一个最小堆，其中最小的元素具有最高优先级。您可以自定义比较函数来创建最大堆或基于自定义优先级标准的堆。堆操作（push、pop、peek、replace）都具有 O(log n) 时间复杂度。

注意

• 推入的值不能为 nil
• 索引从 1 开始（Lua 约定）
• 在空堆上调用 pop() 会导致错误
• length() 是一个函数，不是属性，所以使用 h.length() 而不是 h.length