This library provides heap data structure and its operations. The implementation of heap is Fibonacci heap. Running time of heap operations are followings;
Insert(key, data): O(1)
FindMin(): O(1)
DeleteMin(): Amortized O(log n)
Delete(node): Amortized O(log n)
DecreaseKey(node): Amortized O(1)
Merge(heap1, heap2): O(1)
Search(key): O(n)
A class of Fibonacci heap.
Return #t if obj is a heap, otherwise #f.
compare must be a procedure which takes 2 argument and returns an exact integer indicates the order of given arguments.
Creates a heap.
Creates copy of heap.
compare must be a procedure which takes 2 argument and returns an exact integer indicates the order of given arguments.
Creates a heap whose keys and values are car/cdr part of alist.
Returns #t if heap is empty, otherwise #f.
Returns the number of entries of heap.
Returns comparison procedure of heap.
Returns #t if obj is a heap entry, otherwise #f.
Returns key and value of entry, respectively.
Sets value as entry's value.
Returns the smallest entry of heap. If heap is empty, then #f is returned.
To get the key and value from the returning entry, use heap-entry-keyand heap-entry-value procedures, respectively.
Inserts an entry whose key is key, value is value and returns the entry.
Removes smallest entry and returns it. It is an error if _heap_is empty.
Removes target entry/key from heap and returns the removed entry.
If entry/key is an entry then this operation is done in amortized O(log n). If not, then O(n).
NOTE: If entry/key is an entry, then it must exist in heap. However the procedure won't check so it is user's responsibility to make sure.
Change the key value of given entry/key to new-key. The
new-key must be smaller than current key in sense of the returning
value of heap-compare, otherwise it's an error.
If entry/key is an entry then this operation is done in amortized O(log n). If not, then O(n).
NOTE: If entry/key is an entry, then it must exist in heap. However the procedure won't check so it is user's responsibility to make sure.
Clears all entry of heap and returns heap.
Merge heap2 into heap1 and empty it. Then returns heap1.
This procedure changes both heaps destructively, if you want to kepp
heap2 intact, use merge-heaps or merge-heaps! instead.
Merges heap and returns merged heap.
If the first procedure is used then the returning heap is freshly created according to heap1. The second form merged the rest of heaps to heap1.
The running time of these procedures is O(nm) where m is number of heaps to merge.
Returns entry value associated with key in heap. If there is no entry, then fallback is returned.
The running time of this procedures is O(n).
proc must be a procedure accepts one argument.
Updates the entry value associated to key with the returned value of proc. If the entry doesn't exist then default will be passed to the proc.
The running time of this procedures is O(n).
Searches the entry associated to key and returns it. If there is no entry then #f is returned.
If optional argument finish given then it must be a procedure which takes one argument. The procedure is called when search process is finished. The given argument is either an entry of #f.