Abstract data type "Heap"
This functionality does not run in MATLAB.
adt::Heap implements the abstract data type
A "heap" or "priority queue" is a data type that stores a collection of elements. Elements can be compared and the minimal element can be read and deleted from the heap.
adt::Heap, each element is associated
with a comparison key, typically a real number. The keys must be comparable
with one another using
To get access to the largest element in an
you can simply negate the comparison keys.
adt::Heap returns a function
environment. This object has slots
"delete_min" which allow operations on the
heap. See the examples.
adt::Heap does not allow access to other
elements than the minimal one.
adt::Heap() creates an empty heap:
h := adt::Heap()
the number of elements in the heap:
h::insert is the method to insert new elements.
It expects two arguments: the comparison key and the data. For now,
we simply insert some numbers, so we repeat the number in both arguments:
h::insert(3,3): h::insert(1,1): h::insert(2,2):
When retrieving the elements with
we see that they are returned in increasing order:
h::delete_min(), h::delete_min(), h::delete_min()
The heap is now empty:
delete_min on an empty heap returns
adt::Heap uses a complete binary tree stored
in a list. Insertions operate in expected
constant time, with a worst case time logarithmic in the number of
elements in the heap. For
"delete_min", both the
average and the worst-case running time are O(log n),
with n the
size of the heap.