【高级技巧】堆排序：TopK筛选的堆实现封装

local heap = {}
local function siftDown(arr, i, n)
    while 2 * i <= n do
        local child = 2 * i
        if child < n and arr[child].dmg > arr[child + 1].dmg then
            child = child + 1
        end
        if arr[i].dmg <= arr[child].dmg then
            break
        end
        arr[i], arr[child] = arr[child], arr[i]
        i = child
    end
end
local function topK(records, k)
    local h = {}
    for i = 1, k do
        h[i] = records[i]
        local pos = i
        while pos > 1 and h[pos].dmg < h[math.floor(pos / 2)].dmg do
            local p = math.floor(pos / 2)
            h[pos], h[p] = h[p], h[pos]
            pos = p
        end
    end
    for i = k + 1, #records do
        if records[i].dmg > h[1].dmg then
            h[1] = records[i]
            siftDown(h, 1, k)
        end
    end
    return h
end

local records = {}
for i = 1, 10000 do
    records[i] = { name = "玩家" .. i, dmg = math.random(1, 999999) }
end
local top = topK(records, 100)