<p>A <em>heap</em> is a tree datastructure such that for any child <span class="SimpleMath">\(C\)</span> of a node <span class="SimpleMath">\(N\)</span> it holds that <span class="SimpleMath">\(C \leq N\)</span>, according to some ordering relation <span class="SimpleMath">\(\leq\)</span>.</p>
<p>The fundamental operations for heaps are Construction, <code class="code">Push</code>ing data onto the heap, <code class="code">Peek</code>ing at the topmost item, and <code class="code">Pop</code>ping the topmost item off of the heap.</p>
<p>For a good heap implementation these basic operations should not exceed <span class="SimpleMath">\(O(\log n)\)</span> in runtime where <span class="SimpleMath">\(n\)</span> is the number of items on the heap.</p>
<p>We currently provide two types of heaps: Binary Heaps <a href="chap3_mj.html#X7A01096286198C96"><span class="RefLink">3.3</span></a> and Pairing Heaps <a href="chap3_mj.html#X82EFFA948516AD5C"><span class="RefLink">3.4</span></a>.</p>
<p>The following code shows how to use a binary heap.</p>
<p>For the purposes of the <strong class="pkg">datastructures</strong>, we provide a category <code class="func">IsHeap</code> (<a href="chap3_mj.html#X85D1DDCF86FD53EB"><span class="RefLink">3.2-1</span></a>) . Every implementation of a heap in the category <code class="func">IsHeap</code> (<a href="chap3_mj.html#X85D1DDCF86FD53EB"><span class="RefLink">3.2-1</span></a>) must follow the API described in this section.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Peek</code>( <var class="Arg">heap</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Inspect the item at the top of <var class="Arg">heap</var>.</p>
<p>A binary heap employs a binary tree as its underlying tree datastructure. The implemenataion of binary heaps in <strong class="pkg">datastructures</strong> stores this tree in a flat array which makes it a very good and fast default choice for general purpose use. In particular, even though other heap implementations have better theoretical runtime bounds, well-tuned binary heaps outperform them in many applications.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BinaryHeap</code>( [<var class="Arg">isLess</var>[, <var class="Arg">data</var>]] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A binary heap</p>
<p>Constructor for binary heaps. The optional argument <var class="Arg">isLess</var> must be a binary function that performs comparison between two elements on the heap, and returns <code class="keyw">true</code> if the first argument is less than the second, and <code class="keyw">false</code> otherwise. Using the optional argument <var class="Arg">data</var> the user can give a collection of initial values that are pushed on the stack after construction.</p>
<p>A pairing heap is a heap datastructure with a very simple implementation in terms of <strong class="pkg">GAP</strong> lists. <code class="code">Push</code> and <code class="code">Peek</code> have <span class="SimpleMath">\(O(1)\)</span> complexity, and <code class="code">Pop</code> has an amortized amortised O(log n), where <span class="SimpleMath">\(n\)</span> is the number of items on the heap.</p>
<p>For a reference see <a href="chapBib_mj.html#biBFredman1986">[FSST86]</a>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PairingHeap</code>( [<var class="Arg">isLess</var>[, <var class="Arg">data</var>]] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A pairing heap</p>
<p>Constructor for pairing heaps. The optional argument <var class="Arg">isLess</var> must be a binary function that performs comparison between two elements on the heap, and returns <code class="keyw">true</code> if the first argument is less than the second, and <code class="keyw">false</code> otherwise. Using the optional argument <var class="Arg">data</var> the user can give a collection of initial values that are pushed on the stack after construction.</p>
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
