Lua最小堆：上浮下沉的完全二叉树

flowchart TD
A[新数从末位入堆] --> B{比父亲小}
B -- 是 --> C[与父亲换位 继续上浮]
B -- 否 --> D[停 浮到位]
C --> B
E[出堆 堆顶离场] --> F[末位补到顶]
F --> G{比小的子大}
G -- 是 --> H[与较小的子换位 继续下沉]
G -- 否 --> I[停 沉到位]
H --> G

 fx-minheap

-- @file MinHeap.lua
-- 最小堆 —— 上浮下沉的完全二叉树

local MinHeap = {}

local CONST = {
    HEAP_CAP      = 64,

    AUTOINC_BASE  = 1143000,
}

local _heap      = {}
local _count     = 0
local _compare   = nil

local function ShowTip(msg)
    if msg and msg ~= "" then SL:ShowSystemTips(msg) end
end

local function ParentOf(i)
    return math.floor((i - 1) / 2)
end

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

local function RightOf(i)
    return 2 * i + 2
end

local function Less(a, b)
    if _compare then
        return _compare(_heap[a], _heap[b])
    end
    return _heap[a] < _heap[b]
end

function MinHeap.Count()
    return _count
end

function MinHeap.Peek()
    return _heap[0]
end

-- 上浮：新数从末位一路跟父亲比
local function Swim(i)
    while i > 0 do
        local p = ParentOf(i)
        if Less(i, p) then
            _heap[i], _heap[p] = _heap[p], _heap[i]
            i = p
        else
            break
        end
    end
end

-- 下沉：补顶的数一路跟较小的子比
local function Sink(i)
    while true do
        local l = LeftOf(i)
        local r = RightOf(i)
        local m = i
        if l < _count and Less(l, m) then m = l end
        if r < _count and Less(r, m) then m = r end
        if m == i then break end
        _heap[i], _heap[m] = _heap[m], _heap[i]
        i = m
    end
end

function MinHeap.Push(value)
    if _count >= CONST.HEAP_CAP then
        ShowTip("堆满了——出几个再入")
        return false
    end
    _heap[_count] = value
    Swim(_count)
    _count = _count + 1
    return true
end

function MinHeap.Pop()
    if _count == 0 then return nil end
    local top = _heap[0]
    _count = _count - 1
    _heap[0] = _heap[_count]
    _heap[_count] = nil
    Sink(0)
    return top
end

function MinHeap.BindCompare(func)
    _compare = func
end

SL:ScheduleOnce(function()
    SL:BindDebugButton("演示入堆", function()
        MinHeap.Push(math.random(10, 99))
    end)
    SL:BindDebugButton("演示出堆", function()
        MinHeap.Pop()
    end)
    ShowTip("技能已加载: 最小堆 (调试按钮触发)")
end, 1.0)

function MinHeap.Unload()
    _heap = {}
    _count = 0
    _compare = nil
end

return MinHeap