heap_swap

内部接口，交换堆中两个节点

local function heap_swap(list, i, j)
    local temp = list[i]
    list[i] = list[j]
    list[j] = temp
    list[i].index = i
    list[j].index = j
end

heap_up

内部接口，当修改节点导致不再满足堆的性质时调用，将不断与上层节点交换直至满足堆的性质

local function heap_up(list, index)
    local parent_index
    while index > 1 do
        parent_index = math.floor(index / 2)
        if list[index].priority >= list[parent_index].priority then
            break
        end
        heap_swap(list, index, parent_index)
        index = parent_index
    end
end

heap_down

内部接口，当修改节点导致不再满足堆的性质时调用，将不断与下层节点交换直至满足堆的性质

local function heap_down(list, index)
    local child_index1, child_index2, min_index
    local len = #list
    while true do
        child_index1 = index * 2
        child_index2 = child_index1 + 1
        if child_index1 > len then
            break
        elseif child_index1 == len then
            min_index = len
        else
            min_index = child_index1
            if list[child_index2].priority < list[child_index1].priority then
                min_index = child_index2
            end
        end
        if list[index].priority <= list[min_index].priority then
            break
        end
        heap_swap(list, index, min_index)
        index = min_index
    end
end

heap_pop

提供给外部的api，移除堆中最小节点

function _M.pop(list)
    if #list == 0 then
        return nil, nil
    end
    local res = list[1]
    heap_swap(list, 1, #list)
    list[#list] = nil
    heap_down(list, 1)
    return res.priority, res.data
end

heap_push

提供给外部的api，插入新节点

function _M.push(list, priority, data)
    local index = #list + 1
    local node = {
        priority = priority,
        data = data,
        index = index
    }
    list[index] = node
    heap_up(list, index)
    return node
end

heap_delete

提供给外部的api，移除任意位置的节点

heap_pop也相当于heap_delete(list, 1)

function _M.delete(list, index)
    if index > #list then
        return
    end
    heap_swap(list, index, #list)
    list[#list] = nil
    local parent_index = math.floor(index / 2)
    if parent_index > 0 and list[parent_index].priority > list[index].priority then
        heap_up(list, index)
    else
        heap_down(list, index)
    end
end