Module binaryheap
Binary heap implementation
Original code by Oliver Kroth, with extras as proposed by Sean Conner.
The 'plain binary heap' is managed by positions. Which are hard to get once an element is inserted. It can be anywhere in the list because it is re-sorted upon insertion/deletion of items.
A 'unique binary heap' is where the payload is unique and the payload itself also stored (as key) in the heap with the position as value, as in;
heap.reverse[payload] = [pos]
Due to this setup the reverse search, based on payload
, is now a
much faster operation because instead of traversing the list/heap, you can do;
pos = heap.reverse[payload]
This means that deleting elements from a 'unique binary heap' is faster than from a plain heap.
All management functions in the 'unique binary heap' take payload
instead of pos
as argument.
Note that the value of the payload must be unique!
Functions
binaryHeap (swap, lt, lte) | Creates a new binary heap. |
heap:insert (value, payload) | Inserts an element in the heap. |
heap:peek () | Returns the element at the top of the heap, without removing it. |
heap:pop () | Removes the top of the heap and returns it. |
heap:pop () | Removes the top of the heap and returns it. |
heap:remove (pos) | Removes an element from the heap. |
heap:update (pos, newValue) | Updates the value of an element in the heap. |
maxHeap () | Creates a new max-heap. |
maxUnique () | Creates a new max-heap with unique payloads. |
minHeap () | Creates a new min-heap. |
minUnique () | Creates a new min-heap with unique payloads. |
Functions
- binaryHeap (swap, lt, lte)
-
Creates a new binary heap.
This is the core of all heaps, the others are built upon these sorting functions.Parameters:
- swap
(function)
swap(heap, idx1, idx2)
swaps values atidx1
andidx2
in the heapsv
andpl
lists
. - lt
(function) in
lt(a, b)
returnstrue
whena < b
(for a min-heap) - lte
(function) in
lte(a,b)
returnstrue
whena <= b
(for a min-heap)
Returns:
-
table with two methods;
tbl:bubbleUp(pos)
andtbl:sinkDown(pos)
that implement the sorting algorithm and two fields;tbl.value
andtbl.payload
being lists, holding the values and payloads respectively. - swap
(function)
- heap:insert (value, payload)
-
Inserts an element in the heap.
Parameters:
- value the value used for sorting this element
- payload the payload attached to this element
- heap:peek ()
-
Returns the element at the top of the heap, without removing it.
When used with timers, peek will tell when the next timer is due.
Returns:
-
value + payload at the top, or
nil
if there is noneUsage:
-- simple timer based heap example while true do sleep(heap:peek() - gettime()) -- assume LuaSocket gettime function coroutine.resume((heap:pop())) -- assumes payload to be a coroutine, double parens to drop extra return value end
- heap:pop ()
-
Removes the top of the heap and returns it.
When used with timers, pop will return the payload that is due.
Note: this function returns
payload
as the first result to prevent extra locals when retrieving thepayload
.Returns:
-
payload + value at the top, or
nil
if there is none - heap:pop ()
-
Removes the top of the heap and returns it.
When used with timers, pop will return the payload that is due.
Note: this function returns
payload
as the first result to prevent extra locals when retrieving thepayload
.Returns:
-
payload + value at the top, or
nil
if there is none - heap:remove (pos)
-
Removes an element from the heap.
Parameters:
- pos the position to remove
Returns:
-
payload, value or nil + error if an illegal
pos
value was provided - heap:update (pos, newValue)
-
Updates the value of an element in the heap.
Parameters:
- pos the position which value to update
- newValue the new value to use for this payload
- maxHeap ()
-
Creates a new max-heap. A max-heap is where the largest value is at the top.
Returns:
-
the new heap
- maxUnique ()
-
Creates a new max-heap with unique payloads. A max-heap is where the largest value is at the top.
NOTE: All management functions in the 'unique binary heap' take
payload
instead ofpos
as argument.Returns:
-
the new heap
- minHeap ()
-
Creates a new min-heap. A min-heap is where the smallest value is at the top.
Returns:
-
the new heap
- minUnique ()
-
Creates a new min-heap with unique payloads. A min-heap is where the smallest value is at the top.
NOTE: All management functions in the 'unique binary heap' take
payload
instead ofpos
as argument.Returns:
-
the new heap