lua-users home
lua-l archive

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

On Mon, Apr 13, 2015 at 8:17 AM, Oliver Kroth <> wrote:
> Hi Thijs,
> not sure if someone else referred to a solution like mine:
> I used in one of my projects a so called binary heap as "queue". New events
> are inserted at the end and bubbled up. Deleted timers leave a hole that is
> filled by inserting the last element and resort the heap. Checking whether
> the first (earliest) event is due can be done in O(1) by looking on the
> heap's root. Inserting and deleting events can be done in O(log n). The
> funny thing is that the heap does not use pointers but is stored in a
> contiguous array using the event's index to calculate the parent's and
> children's indexes.
> May not be the most efficient solution but had the smallest overhead on
> checking the due events, and has reasonable effort on queue management.
> The Lua implementations is about 100 LOC.
> If someone is interested, I may post it.
> --
> Oliver Kroth

I am interested. Could you post it, please?

Best regards,
Boris Nagaev