tieske / binaryheap.lua Goto Github PK

see https://tieske.github.io/binaryheap.lua/#heap:pop

requires additional tests, and no length checking on the payload table as it is no longer a valid list/array

using 1 table with a table of value and payload for each element, is probably less efficient than using two tables, one for values, the other for payloads.

see #1 (comment)

The documentation mentions field "reverse", which does not exist. There are fields "value" and "reverse". I think, they should be renamed to "values" and "reverse".

Method remove behaves in different way in plain heap and in unique heap. I think it should be replaced with two methods:

• removePos(pos)
• removePayload(payload)

These two methods are better than ambigous remove method.

Same considerations for update method.

Can not find it on http://tieske.github.io/binaryheap.lua/index.html

It is actually a plain heap with map from values to positions. This if often needed.

-- Note: this function returns `payload` as the first result to prevent
-- extra locals when retrieving the `payload`.
-- @return value, payload at the top, or `nil` if there is none
function popU(self)
  if self.values[1] then
    local payload = self.payloads[1]
    local value = remove(self, 1)
    return value, payload
  end
end

The comment+docs say that payload is returned first; yet the code returns value. Which is it meant to be?

It fails even on Travis CI configured for your project: https://travis-ci.com/Tieske/binaryheap.lua/jobs/177798107.

Method remove returns (payload, value).
Method pop returns (payload, value).
Method peek returns (value, payload).

I think, all these methods should return (value, payload), because all heaps have values, but some heaps do not have payloads.