Re: Speed query

["Javier Guerra" <javier@...>]

ok, i wrote the 'h:reheapify()' function:

function heap:reheapify ()
	local cmp = self.comparison
	local ssize = #self
	local i = math_floor (ssize/2)
	local j = i*2
	while i > 0 do
		local j2 = j
		if j2+1 <= ssize and cmp (self[j2+1].key, self[j2].key) then
			j2 = j2+1
		end
		if cmp (self[j2].key, self[i].key) then
			local r = self[j2]
			self[j2] = self[i]
			self[i] = r
		end
		i = i -1
		j = j - 2
	end
end

so now the tests can sloppily insert items at the end, and just call
h:reheapify() before popping them (what i called a 'lazy heap').  that
creates a performance profile similar to the sort()ed queue: with many
small cycles it's far worse, with few large cycles it's a little
better.

but also noted that your speed test of the sort()ed queue just inserts
numbers in the queue, while the heap uses a {key,value} table for each
item... no fair!

with the overhead of creating a table per item, and using a Lua
callback for sorting... it's far,far worse than a heap, both lazy and
eager!

-- 
Javier