binaryheap.lua

Contents

• Functions

Modules

• binaryheap

Topics

• readme

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 at idx1 and idx2 in the heaps v and pl lists.
• lt (function) in lt(a, b) returns true when a < b (for a min-heap)
• lte (function) in lte(a,b) returns true when a <= b (for a min-heap)

Returns:

table with two methods; tbl:bubbleUp(pos) and tbl:sinkDown(pos) that implement the sorting algorithm and two fields; tbl.value and tbl.payload being lists, holding the values and payloads respectively.

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 none

Usage:

 -- 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 the payload.

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 the payload.

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 of pos 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 of pos as argument.

Returns:

the new heap