【Lua实战】二叉堆：伤害排行榜的有序插入

-- 小顶堆：容量固定，只保留最大的十条记录
local heap = {n = 0}
local function siftUp(h, i)
    while i > 1 do
        local p = math.floor(i / 2)
        if h[p].dmg <= h[i].dmg then break end
        h[p], h[i] = h[i], h[p]
        i = p
    end
end
local function siftDown(h, i)
    while i * 2 <= h.n do
        local c = i * 2
        if c + 1 <= h.n and h[c + 1].dmg < h[c].dmg then c = c + 1 end
        if h[i].dmg <= h[c].dmg then break end
        h[i], h[c] = h[c], h[i]
        i = c
    end
end

-- 伤害入堆：超过容量先和堆顶比较
local function pushDamage(name, dmg)
    local item = {name = name, dmg = dmg}
    if heap.n < 10 then
        heap.n = heap.n + 1
        heap[heap.n] = item
        siftUp(heap, heap.n)
    elseif dmg > heap[1].dmg then
        heap[1] = item
        siftDown(heap, 1)
    end
end
-- QF触发: killmon 首领倒下后广播榜单
local player = class(actor)
local snap = {}
for i = 1, heap.n do snap[i] = heap[i] end
table.sort(snap, function(a, b) return a.dmg > b.dmg end)
local lines = {}
for i = 1, #snap do
    lines[#lines + 1] = snap[i].name .. "：" .. snap[i].dmg
end
sendmsg(player, 1, 0, table.concat(lines, " "))