lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

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
		if cmp (self[j2].key, self[i].key) then
			local r = self[j2]
			self[j2] = self[i]
			self[i] = r
		i = i -1
		j = j - 2

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

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