Abstract data type "Heap"
This functionality does not run in MATLAB.
adt::Heap implements the abstract data type "Heap".
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.
In 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 adt::Heap, you can simply negate the comparison keys.
adt::Heap returns a function environment. This object has slots "insert", "nops", "min_pair", "min_element", and "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 slot "nops" of h shows 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 h::delete_min, we see that they are returned in increasing order:
h::delete_min(), h::delete_min(), h::delete_min()
The heap is now empty:
Calling delete_min on an empty heap returns FAIL:
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.