heap - Maple Help

heap

Priority Queue Data Structure

 Calling Sequence heap[new](f) heap[new](f, x1, ..., xn) heap[insert](x, h) heap[extract](h) heap[empty](h) heap[max](h) heap[size](h)

Parameters

 f - Boolean-valued function h - heap x, x[i] - values to be inserted into the heap

Description

 • The call heap[new](f) returns an empty heap where f is a Boolean-valued function which specifies a total ordering for the elements to be inserted into the heap.
 • The call heap[new](f, x1, ..., xn) returns a heap with the values x1, ..., xn initially inserted into the heap.
 • The call heap[insert](x, h) inserts the element x into the heap h while heap[extract](h) returns (and removes) the maximum element from the heap (according to the ordering defined by f).
 • The call heap[empty](h) returns true if the heap h is empty, and false if it is not empty.
 • Additionally, heap[max](h) returns the maximum element in the heap (but does not remove it) and heap[size](h) returns the number of elements in the heap.

Examples

 > $h≔\mathrm{heap}\left[\mathrm{new}\right]\left(\mathrm{lexorder},\mathrm{greg},\mathrm{tony},\mathrm{bruno},\mathrm{michael}\right):$
 > $\mathrm{heap}\left[\mathrm{insert}\right]\left(\mathrm{stefan},h\right)$
 ${\mathrm{stefan}}$ (1)
 > $\mathrm{heap}\left[\mathrm{size}\right]\left(h\right)$
 ${5}$ (2)
 > $\mathrm{heap}\left[\mathrm{max}\right]\left(h\right)$
 ${\mathrm{tony}}$ (3)
 > $\mathbf{while}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{not}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathrm{heap}\left[\mathrm{empty}\right]\left(h\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\mathrm{heap}\left[\mathrm{extract}\right]\left(h\right)\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}$
 ${\mathrm{tony}}$
 ${\mathrm{stefan}}$
 ${\mathrm{michael}}$
 ${\mathrm{greg}}$
 ${\mathrm{bruno}}$ (4)
 >