703 lines
16 KiB
HTML
703 lines
16 KiB
HTML
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
|
|
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
|
|
<html>
|
|
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
|
|
<head>
|
|
<title>binaryheap</title>
|
|
<link rel="stylesheet" href="ldoc.css" type="text/css" />
|
|
</head>
|
|
<body>
|
|
|
|
<div id="container">
|
|
|
|
<div id="product">
|
|
<div id="product_logo"></div>
|
|
<div id="product_name"><big><b></b></big></div>
|
|
<div id="product_description"></div>
|
|
</div> <!-- id="product" -->
|
|
|
|
|
|
<div id="main">
|
|
|
|
|
|
<!-- Menu -->
|
|
|
|
<div id="navigation">
|
|
<br/>
|
|
<h1>binaryheap.lua</h1>
|
|
|
|
|
|
<h2>Contents</h2>
|
|
<ul>
|
|
<li><a href="#Basic_heap">Basic heap </a></li>
|
|
<li><a href="#Plain_heap">Plain heap </a></li>
|
|
<li><a href="#Unique_heap">Unique heap </a></li>
|
|
</ul>
|
|
|
|
|
|
<h2>Modules</h2>
|
|
<ul class="nowrap">
|
|
<li><strong>binaryheap</strong></li>
|
|
</ul>
|
|
<h2>Topics</h2>
|
|
<ul class="">
|
|
<li><a href="topics/readme.md.html">readme</a></li>
|
|
</ul>
|
|
|
|
</div>
|
|
|
|
<div id="content">
|
|
|
|
<h1>Module <code>binaryheap</code></h1>
|
|
<p>Binary heap implementation</p>
|
|
|
|
<p> A binary heap (or binary tree) is a <a href="http://en.wikipedia.org/wiki/Binary_heap">sorting algorithm</a>.</p>
|
|
<p>
|
|
|
|
|
|
<p> 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. The array with values is stored in field
|
|
<code>values</code>:</p>
|
|
|
|
|
|
<pre>
|
|
<span class="backtick"><code>peek = heap.values[1]</code></span>
|
|
</pre>
|
|
|
|
<p> 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;</p>
|
|
|
|
<pre>
|
|
<span class="backtick"><code>heap.reverse[payload] = [pos]</code></span>
|
|
</pre>
|
|
|
|
<p> 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;</p>
|
|
|
|
<pre>
|
|
<span class="backtick"><code>pos = heap.reverse[payload]</code></span>
|
|
</pre>
|
|
|
|
<p> This means that deleting elements from a 'unique binary heap' is
|
|
faster than from a plain heap.</p>
|
|
|
|
<p> All management functions in the 'unique binary heap' take <code>payload</code>
|
|
instead of <code>pos</code> as argument.
|
|
Note that the value of the payload must be unique!</p>
|
|
|
|
<p> Fields of heap object:</p>
|
|
|
|
<ul>
|
|
<li>values - array of values</li>
|
|
<li>payloads - array of payloads (unique binary heap only)</li>
|
|
<li>reverse - map from payloads to indices (unique binary heap only)</li>
|
|
</ul>
|
|
</p>
|
|
|
|
|
|
<h2><a href="#Basic_heap">Basic heap </a></h2>
|
|
<table class="function_list">
|
|
<tr>
|
|
<td class="name" nowrap><a href="#binaryHeap">binaryHeap (swap, erase, lt)</a></td>
|
|
<td class="summary">Creates a new binary heap.</td>
|
|
</tr>
|
|
</table>
|
|
<h2><a href="#Plain_heap">Plain heap </a></h2>
|
|
<table class="function_list">
|
|
<tr>
|
|
<td class="name" nowrap><a href="#heap:insert">heap:insert (value)</a></td>
|
|
<td class="summary">Inserts an element in the heap.</td>
|
|
</tr>
|
|
<tr>
|
|
<td class="name" nowrap><a href="#heap:peek">heap:peek ()</a></td>
|
|
<td class="summary">Returns the element at the top of the heap, without removing it.</td>
|
|
</tr>
|
|
<tr>
|
|
<td class="name" nowrap><a href="#heap:pop">heap:pop ()</a></td>
|
|
<td class="summary">Removes the top of the heap and returns it.</td>
|
|
</tr>
|
|
<tr>
|
|
<td class="name" nowrap><a href="#heap:remove">heap:remove (pos)</a></td>
|
|
<td class="summary">Removes an element from the heap.</td>
|
|
</tr>
|
|
<tr>
|
|
<td class="name" nowrap><a href="#heap:size">heap:size ()</a></td>
|
|
<td class="summary">Returns the number of elements in the heap.</td>
|
|
</tr>
|
|
<tr>
|
|
<td class="name" nowrap><a href="#heap:update">heap:update (pos, newValue)</a></td>
|
|
<td class="summary">Updates the value of an element in the heap.</td>
|
|
</tr>
|
|
<tr>
|
|
<td class="name" nowrap><a href="#maxHeap">maxHeap (gt)</a></td>
|
|
<td class="summary">Creates a new max-heap, where the largest value is at the top.</td>
|
|
</tr>
|
|
<tr>
|
|
<td class="name" nowrap><a href="#minHeap">minHeap (lt)</a></td>
|
|
<td class="summary">Creates a new min-heap, where the smallest value is at the top.</td>
|
|
</tr>
|
|
</table>
|
|
<h2><a href="#Unique_heap">Unique heap </a></h2>
|
|
<table class="function_list">
|
|
<tr>
|
|
<td class="name" nowrap><a href="#heap:size">heap:size ()</a></td>
|
|
<td class="summary">Returns the number of elements in the heap.</td>
|
|
</tr>
|
|
<tr>
|
|
<td class="name" nowrap><a href="#maxUnique">maxUnique (gt)</a></td>
|
|
<td class="summary">Creates a new max-heap with unique payloads.</td>
|
|
</tr>
|
|
<tr>
|
|
<td class="name" nowrap><a href="#minUnique">minUnique (lt)</a></td>
|
|
<td class="summary">Creates a new min-heap with unique payloads.</td>
|
|
</tr>
|
|
<tr>
|
|
<td class="name" nowrap><a href="#unique:insert">unique:insert (value, payload)</a></td>
|
|
<td class="summary">Inserts an element in the heap.</td>
|
|
</tr>
|
|
<tr>
|
|
<td class="name" nowrap><a href="#unique:peek">unique:peek ()</a></td>
|
|
<td class="summary">Returns the element at the top of the heap, without removing it.</td>
|
|
</tr>
|
|
<tr>
|
|
<td class="name" nowrap><a href="#unique:peekValue">unique:peekValue ()</a></td>
|
|
<td class="summary">Returns the element at the top of the heap, without removing it.</td>
|
|
</tr>
|
|
<tr>
|
|
<td class="name" nowrap><a href="#unique:pop">unique:pop ()</a></td>
|
|
<td class="summary">Removes the top of the heap and returns it.</td>
|
|
</tr>
|
|
<tr>
|
|
<td class="name" nowrap><a href="#unique:remove">unique:remove (payload)</a></td>
|
|
<td class="summary">Removes an element from the heap.</td>
|
|
</tr>
|
|
<tr>
|
|
<td class="name" nowrap><a href="#unique:update">unique:update (payload, newValue)</a></td>
|
|
<td class="summary">Updates the value of an element in the heap.</td>
|
|
</tr>
|
|
<tr>
|
|
<td class="name" nowrap><a href="#unique:valueByPayload">unique:valueByPayload (payload)</a></td>
|
|
<td class="summary">Returns the value associated with the payload</td>
|
|
</tr>
|
|
</table>
|
|
|
|
<br/>
|
|
<br/>
|
|
|
|
|
|
<h2 class="section-header has-description"><a name="Basic_heap"></a>Basic heap </h2>
|
|
|
|
<div class="section-description">
|
|
This is the base implementation of the heap. Under regular circumstances
|
|
this should not be used, instead use a <em>Plain heap</em> or <em>Unique heap</em>.
|
|
</div>
|
|
<dl class="function">
|
|
<dt>
|
|
<a name = "binaryHeap"></a>
|
|
<strong>binaryHeap (swap, erase, lt)</strong>
|
|
</dt>
|
|
<dd>
|
|
Creates a new binary heap.
|
|
This is the core of all heaps, the others
|
|
are built upon these sorting functions.
|
|
|
|
|
|
<h3>Parameters:</h3>
|
|
<ul>
|
|
<li><span class="parameter">swap</span>
|
|
(function) <code>swap(heap, idx1, idx2)</code> swaps values at
|
|
<code>idx1</code> and <code>idx2</code> in the heaps <code>heap.values</code> and <code>heap.payloads</code> lists (see
|
|
return value below).
|
|
</li>
|
|
<li><span class="parameter">erase</span>
|
|
(function) <code>swap(heap, position)</code> raw removal
|
|
</li>
|
|
<li><span class="parameter">lt</span>
|
|
(function) in <code>lt(a, b)</code> returns <code>true</code> when <code>a < b</code> (for a min-heap)
|
|
</li>
|
|
</ul>
|
|
|
|
<h3>Returns:</h3>
|
|
<ol>
|
|
|
|
table with two methods; <code>heap:bubbleUp(pos)</code> and <code>heap:sinkDown(pos)</code>
|
|
that implement the sorting algorithm and two fields; <code>heap.values</code> and
|
|
<code>heap.payloads</code> being lists, holding the values and payloads respectively.
|
|
</ol>
|
|
|
|
|
|
|
|
|
|
</dd>
|
|
</dl>
|
|
<h2 class="section-header has-description"><a name="Plain_heap"></a>Plain heap </h2>
|
|
|
|
<div class="section-description">
|
|
A plain heap carries a single piece of information per entry. This can be
|
|
any type (except <code>nil</code>), as long as the comparison function used to create
|
|
the heap can handle it.
|
|
</div>
|
|
<dl class="function">
|
|
<dt>
|
|
<a name = "heap:insert"></a>
|
|
<strong>heap:insert (value)</strong>
|
|
</dt>
|
|
<dd>
|
|
Inserts an element in the heap.
|
|
|
|
|
|
<h3>Parameters:</h3>
|
|
<ul>
|
|
<li><span class="parameter">value</span>
|
|
the value used for sorting this element
|
|
</li>
|
|
</ul>
|
|
|
|
<h3>Returns:</h3>
|
|
<ol>
|
|
|
|
nothing, or throws an error on bad input
|
|
</ol>
|
|
|
|
|
|
|
|
|
|
</dd>
|
|
<dt>
|
|
<a name = "heap:peek"></a>
|
|
<strong>heap:peek ()</strong>
|
|
</dt>
|
|
<dd>
|
|
Returns the element at the top of the heap, without removing it.
|
|
|
|
|
|
|
|
<h3>Returns:</h3>
|
|
<ol>
|
|
|
|
value at the top, or <code>nil</code> if there is none
|
|
</ol>
|
|
|
|
|
|
|
|
|
|
</dd>
|
|
<dt>
|
|
<a name = "heap:pop"></a>
|
|
<strong>heap:pop ()</strong>
|
|
</dt>
|
|
<dd>
|
|
Removes the top of the heap and returns it.
|
|
|
|
|
|
|
|
<h3>Returns:</h3>
|
|
<ol>
|
|
|
|
value at the top, or <code>nil</code> if there is none
|
|
</ol>
|
|
|
|
|
|
|
|
|
|
</dd>
|
|
<dt>
|
|
<a name = "heap:remove"></a>
|
|
<strong>heap:remove (pos)</strong>
|
|
</dt>
|
|
<dd>
|
|
Removes an element from the heap.
|
|
|
|
|
|
<h3>Parameters:</h3>
|
|
<ul>
|
|
<li><span class="parameter">pos</span>
|
|
the position to remove
|
|
</li>
|
|
</ul>
|
|
|
|
<h3>Returns:</h3>
|
|
<ol>
|
|
|
|
value, or nil if a bad <code>pos</code> value was provided
|
|
</ol>
|
|
|
|
|
|
|
|
|
|
</dd>
|
|
<dt>
|
|
<a name = "heap:size"></a>
|
|
<strong>heap:size ()</strong>
|
|
</dt>
|
|
<dd>
|
|
Returns the number of elements in the heap.
|
|
|
|
|
|
|
|
<h3>Returns:</h3>
|
|
<ol>
|
|
|
|
number of elements
|
|
</ol>
|
|
|
|
|
|
|
|
|
|
</dd>
|
|
<dt>
|
|
<a name = "heap:update"></a>
|
|
<strong>heap:update (pos, newValue)</strong>
|
|
</dt>
|
|
<dd>
|
|
Updates the value of an element in the heap.
|
|
|
|
|
|
<h3>Parameters:</h3>
|
|
<ul>
|
|
<li><span class="parameter">pos</span>
|
|
the position which value to update
|
|
</li>
|
|
<li><span class="parameter">newValue</span>
|
|
the new value to use for this payload
|
|
</li>
|
|
</ul>
|
|
|
|
|
|
|
|
|
|
|
|
</dd>
|
|
<dt>
|
|
<a name = "maxHeap"></a>
|
|
<strong>maxHeap (gt)</strong>
|
|
</dt>
|
|
<dd>
|
|
Creates a new max-heap, where the largest value is at the top.
|
|
|
|
|
|
<h3>Parameters:</h3>
|
|
<ul>
|
|
<li><span class="parameter">gt</span>
|
|
(optional) comparison function (greater-than), see <a href="index.html#binaryHeap">binaryHeap</a>.
|
|
</li>
|
|
</ul>
|
|
|
|
<h3>Returns:</h3>
|
|
<ol>
|
|
|
|
the new heap
|
|
</ol>
|
|
|
|
|
|
|
|
|
|
</dd>
|
|
<dt>
|
|
<a name = "minHeap"></a>
|
|
<strong>minHeap (lt)</strong>
|
|
</dt>
|
|
<dd>
|
|
Creates a new min-heap, where the smallest value is at the top.
|
|
|
|
|
|
<h3>Parameters:</h3>
|
|
<ul>
|
|
<li><span class="parameter">lt</span>
|
|
(optional) comparison function (less-than), see <a href="index.html#binaryHeap">binaryHeap</a>.
|
|
</li>
|
|
</ul>
|
|
|
|
<h3>Returns:</h3>
|
|
<ol>
|
|
|
|
the new heap
|
|
</ol>
|
|
|
|
|
|
|
|
|
|
</dd>
|
|
</dl>
|
|
<h2 class="section-header has-description"><a name="Unique_heap"></a>Unique heap </h2>
|
|
|
|
<div class="section-description">
|
|
A unique heap carries 2 pieces of information per entry.</p>
|
|
|
|
<ol>
|
|
<li>The <code>value</code>, this is used for ordering the heap. It can be any type (except
|
|
<code>nil</code>), as long as the comparison function used to create the heap can
|
|
handle it.</li>
|
|
<li>The <code>payload</code>, this can be any type (except <code>nil</code>), but it MUST be unique.</li>
|
|
</ol>
|
|
|
|
<p> With the 'unique heap' it is easier to remove elements from the heap.
|
|
</div>
|
|
<dl class="function">
|
|
<dt>
|
|
<a name = "heap:size"></a>
|
|
<strong>heap:size ()</strong>
|
|
</dt>
|
|
<dd>
|
|
Returns the number of elements in the heap.
|
|
|
|
|
|
|
|
<h3>Returns:</h3>
|
|
<ol>
|
|
|
|
number of elements
|
|
</ol>
|
|
|
|
|
|
|
|
|
|
</dd>
|
|
<dt>
|
|
<a name = "maxUnique"></a>
|
|
<strong>maxUnique (gt)</strong>
|
|
</dt>
|
|
<dd>
|
|
Creates a new max-heap with unique payloads.
|
|
A max-heap is where the largest value is at the top.</p>
|
|
|
|
<p> <em>NOTE</em>: All management functions in the 'unique binary heap'
|
|
take <code>payload</code> instead of <code>pos</code> as argument.
|
|
|
|
|
|
<h3>Parameters:</h3>
|
|
<ul>
|
|
<li><span class="parameter">gt</span>
|
|
(optional) comparison function (greater-than), see <a href="index.html#binaryHeap">binaryHeap</a>.
|
|
</li>
|
|
</ul>
|
|
|
|
<h3>Returns:</h3>
|
|
<ol>
|
|
|
|
the new heap
|
|
</ol>
|
|
|
|
|
|
|
|
|
|
</dd>
|
|
<dt>
|
|
<a name = "minUnique"></a>
|
|
<strong>minUnique (lt)</strong>
|
|
</dt>
|
|
<dd>
|
|
Creates a new min-heap with unique payloads.
|
|
A min-heap is where the smallest value is at the top.</p>
|
|
|
|
<p> <em>NOTE</em>: All management functions in the 'unique binary heap'
|
|
take <code>payload</code> instead of <code>pos</code> as argument.
|
|
|
|
|
|
<h3>Parameters:</h3>
|
|
<ul>
|
|
<li><span class="parameter">lt</span>
|
|
(optional) comparison function (less-than), see <a href="index.html#binaryHeap">binaryHeap</a>.
|
|
</li>
|
|
</ul>
|
|
|
|
<h3>Returns:</h3>
|
|
<ol>
|
|
|
|
the new heap
|
|
</ol>
|
|
|
|
|
|
|
|
|
|
</dd>
|
|
<dt>
|
|
<a name = "unique:insert"></a>
|
|
<strong>unique:insert (value, payload)</strong>
|
|
</dt>
|
|
<dd>
|
|
Inserts an element in the heap.
|
|
|
|
|
|
<h3>Parameters:</h3>
|
|
<ul>
|
|
<li><span class="parameter">value</span>
|
|
the value used for sorting this element
|
|
</li>
|
|
<li><span class="parameter">payload</span>
|
|
the payload attached to this element
|
|
</li>
|
|
</ul>
|
|
|
|
<h3>Returns:</h3>
|
|
<ol>
|
|
|
|
nothing, or throws an error on bad input
|
|
</ol>
|
|
|
|
|
|
|
|
|
|
</dd>
|
|
<dt>
|
|
<a name = "unique:peek"></a>
|
|
<strong>unique:peek ()</strong>
|
|
</dt>
|
|
<dd>
|
|
Returns the element at the top of the heap, without removing it.
|
|
|
|
|
|
|
|
<h3>Returns:</h3>
|
|
<ol>
|
|
|
|
payload, value, or <code>nil</code> if there is none
|
|
</ol>
|
|
|
|
|
|
|
|
|
|
</dd>
|
|
<dt>
|
|
<a name = "unique:peekValue"></a>
|
|
<strong>unique:peekValue ()</strong>
|
|
</dt>
|
|
<dd>
|
|
Returns the element at the top of the heap, without removing it.
|
|
|
|
|
|
|
|
<h3>Returns:</h3>
|
|
<ol>
|
|
|
|
value at the top, or <code>nil</code> if there is none
|
|
</ol>
|
|
|
|
|
|
|
|
<h3>Usage:</h3>
|
|
<ul>
|
|
<pre class="example"><span class="comment">-- simple timer based heap example
|
|
</span><span class="keyword">while</span> <span class="keyword">true</span> <span class="keyword">do</span>
|
|
sleep(heap:peekValue() - gettime()) <span class="comment">-- assume LuaSocket gettime function
|
|
</span> <span class="global">coroutine</span>.resume((heap:pop())) <span class="comment">-- assumes payload to be a coroutine,
|
|
</span> <span class="comment">-- double parens to drop extra return value
|
|
</span><span class="keyword">end</span></pre>
|
|
</ul>
|
|
|
|
</dd>
|
|
<dt>
|
|
<a name = "unique:pop"></a>
|
|
<strong>unique:pop ()</strong>
|
|
</dt>
|
|
<dd>
|
|
Removes the top of the heap and returns it.
|
|
When used with timers, <a href="index.html#unique:pop">pop</a> will return the payload that is due.</p>
|
|
|
|
<p> Note: this function returns <code>payload</code> as the first result to prevent
|
|
extra locals when retrieving the <code>payload</code>.
|
|
|
|
|
|
|
|
<h3>Returns:</h3>
|
|
<ol>
|
|
|
|
payload, value, or <code>nil</code> if there is none
|
|
</ol>
|
|
|
|
|
|
|
|
|
|
</dd>
|
|
<dt>
|
|
<a name = "unique:remove"></a>
|
|
<strong>unique:remove (payload)</strong>
|
|
</dt>
|
|
<dd>
|
|
Removes an element from the heap.
|
|
|
|
|
|
<h3>Parameters:</h3>
|
|
<ul>
|
|
<li><span class="parameter">payload</span>
|
|
the payload to remove
|
|
</li>
|
|
</ul>
|
|
|
|
<h3>Returns:</h3>
|
|
<ol>
|
|
|
|
value, payload or nil if not found
|
|
</ol>
|
|
|
|
|
|
|
|
|
|
</dd>
|
|
<dt>
|
|
<a name = "unique:update"></a>
|
|
<strong>unique:update (payload, newValue)</strong>
|
|
</dt>
|
|
<dd>
|
|
Updates the value of an element in the heap.
|
|
|
|
|
|
<h3>Parameters:</h3>
|
|
<ul>
|
|
<li><span class="parameter">payload</span>
|
|
the payoad whose value to update
|
|
</li>
|
|
<li><span class="parameter">newValue</span>
|
|
the new value to use for this payload
|
|
</li>
|
|
</ul>
|
|
|
|
<h3>Returns:</h3>
|
|
<ol>
|
|
|
|
nothing, or throws an error on bad input
|
|
</ol>
|
|
|
|
|
|
|
|
|
|
</dd>
|
|
<dt>
|
|
<a name = "unique:valueByPayload"></a>
|
|
<strong>unique:valueByPayload (payload)</strong>
|
|
</dt>
|
|
<dd>
|
|
Returns the value associated with the payload
|
|
|
|
|
|
<h3>Parameters:</h3>
|
|
<ul>
|
|
<li><span class="parameter">payload</span>
|
|
the payload to lookup
|
|
</li>
|
|
</ul>
|
|
|
|
<h3>Returns:</h3>
|
|
<ol>
|
|
|
|
value or nil if no such payload exists
|
|
</ol>
|
|
|
|
|
|
|
|
|
|
</dd>
|
|
</dl>
|
|
|
|
|
|
</div> <!-- id="content" -->
|
|
</div> <!-- id="main" -->
|
|
<div id="about">
|
|
<i>generated by <a href="http://github.com/stevedonovan/LDoc">LDoc 1.4.6</a></i>
|
|
<i style="float:right;">Last updated 2018-11-07 17:56:33 </i>
|
|
</div> <!-- id="about" -->
|
|
</div> <!-- id="container" -->
|
|
</body>
|
|
</html>
|