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
|
|
>
|
|
>
|
|
| (1) |
>
|
|
| (2) |
>
|
|
| (3) |
>
|
|
| (4) |
>
|
|
|
|