main.lua

local list = {}
local v_map = {}

local count = 20
math.randomseed(os.time())
local function gen_data()
    for i=1,count do
        local r = math.random(1, 100)
        list[i] = {objid=r}
        v_map[r] = r
    end
end
gen_data()
local function left_i(idx)
	return idx * 2
end
local function right_i(idx)
	return idx * 2 + 1
end
local function parent_i(idx)
	return math.floor(idx / 2)
end
local ret = {}
local role = {}
local func = function(obj, role)
	return obj.objid
end
local n = 3 --max target limit
for i = 1, #list do
	local obj = list[i]
	v_map[obj.objid] = func(obj, role)
	if #ret < n then --向前拱
		local idx = #ret + 1
		ret[idx] = obj
		while idx > 1 do
			local pi = parent_i(idx)
			local child = ret[idx]
			if pi < 1 then
				break
			end
			local po = ret[pi]
			local pv = v_map[po.objid]
			local cv = v_map[child.objid]
			if cv <= pv then
				break
			end
			ret[idx] = po
			ret[pi] = child
			idx = pi
		end
	else
		local v = v_map[obj.objid]
		local hv = v_map[ret[1].objid]
		if v < hv then
			ret[1] = obj
			-- 向下降
			local idx = 1
			while idx < #ret do
				local po = ret[idx]
				local li = left_i(idx)
				local ri = right_i(idx)
				local lo = ret[li]
				local ro = ret[ri]
				if not (lo or ro) then
					break
				end
				local pv = v_map[po.objid]
				local lv = v_map[lo.objid]
				if ro then
					local rv = v_map[ro.objid]
					if rv > lv then -- 选出大的
						lv = rv
						li = ri
						lo = ro
					end
				end
				if pv >= lv then
					break
				end
				-- 交换
				ret[li] = po
				ret[idx] = lo
				idx = li
			end
		end
	end
end
for k, v in ipairs(ret) do
	print(k, v.objid)
end
print("=============== full:")
table.sort(list, function(a, b) return a.objid<b.objid end)
for k, v in ipairs(list) do
    print(k, v.objid)
end