This is the minheap Reference Manual, generated automatically by Declt version 4.0 beta 2 "William Riker" on Wed Mar 15 07:00:26 2023 GMT+0.
minheap/minheap.asdminheap/binary-heap.lispminheap/fib-heap.lispminheap/pairing-heap-elmasri.lispminheap/pairing-heap.lispminheap/pairing-heap-listbased.lispminheap/rank-pairing-heap.lispminheap/rank-pairing-heap-clist.lispminheap/splay-heap.lispminheap/violation-heap.lispThe main system appears first, followed by any subsystem dependency.
minheapVarious heap/priority queue data structures
Stephan Frank <defclass@googlemail.com>
BSD, see LICENSE
binary-heap.lisp (file).
fib-heap.lisp (file).
pairing-heap-elmasri.lisp (file).
pairing-heap.lisp (file).
pairing-heap-listbased.lisp (file).
rank-pairing-heap.lisp (file).
rank-pairing-heap-clist.lisp (file).
splay-heap.lisp (file).
violation-heap.lisp (file).
Files are sorted by type and then listed depth-first from the systems components trees.
minheap/minheap.asdminheap/binary-heap.lispminheap/fib-heap.lispminheap/pairing-heap-elmasri.lispminheap/pairing-heap.lispminheap/pairing-heap-listbased.lispminheap/rank-pairing-heap.lispminheap/rank-pairing-heap-clist.lispminheap/splay-heap.lispminheap/violation-heap.lispminheap/binary-heap.lispminheap (system).
alist-to-heap (function).
binary-heap (class).
clear-heap (function).
decrease-key (function).
empty-p (function).
extract-min (function).
extract-node (function).
heap-size (function).
insert (function).
meld (function).
peek-min (function).
print-object (method).
%make-node (function).
+initial-size+ (constant).
array-index (type).
bin-heap-array (reader method).
(setf bin-heap-array) (writer method).
copy-node (function).
left (function).
node (structure).
node-data (reader).
(setf node-data) (writer).
node-index (reader).
(setf node-index) (writer).
node-key (reader).
(setf node-key) (writer).
node-p (function).
parent (function).
perlocate-up (function).
right (function).
sink (function).
swap-nodes (function).
vector-to-heapvector (function).
minheap/fib-heap.lispminheap (system).
clear-heap (function).
decrease-key (function).
empty-p (function).
extract-min (function).
extract-node (function).
fib-heap (class).
heap-size (reader method).
(setf heap-size) (writer method).
insert (function).
meld (function).
peek-min (function).
print-object (method).
print-object (method).
%make-node (function).
cascading-cut (function).
consolidate (function).
copy-node (function).
cut (function).
link (function).
make-node (function).
min-node (reader method).
(setf min-node) (writer method).
node (structure).
node-child (reader).
(setf node-child) (writer).
node-data (reader).
(setf node-data) (writer).
node-degree (reader).
(setf node-degree) (writer).
node-key (reader).
(setf node-key) (writer).
node-left (reader).
(setf node-left) (writer).
node-mark (reader).
(setf node-mark) (writer).
node-p (function).
node-parent (reader).
(setf node-parent) (writer).
node-right (reader).
(setf node-right) (writer).
splice-lists (function).
minheap/pairing-heap-elmasri.lispminheap (system).
clear-heap (function).
decrease-key (function).
empty-p (function).
extract-min (function).
extract-node (function).
heap-size (function).
insert (function).
meld (function).
pairing-elmasri (class).
peek-min (function).
print-object (method).
%make-node (function).
attach-child (function).
clean-up (function).
combine-siblings (function).
copy-node (function).
cut-parent (function).
delete-node-from-childseq (function).
link (function).
link-children (function).
node (structure).
node-data (reader).
(setf node-data) (writer).
node-key (reader).
(setf node-key) (writer).
node-lchild (reader).
(setf node-lchild) (writer).
node-p (function).
node-parent (reader).
(setf node-parent) (writer).
node-pooled (reader).
(setf node-pooled) (writer).
node-sibling (reader).
(setf node-sibling) (writer).
pair-children (function).
update-decrease (function).
update-min (function).
minheap/pairing-heap.lispminheap (system).
clear-heap (function).
decrease-key (function).
empty-p (function).
extract-min (function).
extract-node (function).
heap-size (function).
insert (function).
meld (function).
pairing-heap (class).
peek-min (function).
print-object (method).
%make-node (function).
attach-child (function).
combine-siblings (function).
copy-node (function).
cut-parent (function).
delete-node-from-childseq (function).
link (function).
link-children (function).
node (structure).
node-data (reader).
(setf node-data) (writer).
node-key (reader).
(setf node-key) (writer).
node-lchild (reader).
(setf node-lchild) (writer).
node-p (function).
node-parent (reader).
(setf node-parent) (writer).
node-sibling (reader).
(setf node-sibling) (writer).
pair-children (function).
minheap/pairing-heap-listbased.lispminheap (system).
clear-heap (function).
decrease-key (function).
empty-p (function).
extract-min (function).
extract-node (function).
heap-size (function).
insert (function).
meld (function).
pairing-heap (class).
peek-min (function).
print-object (method).
%make-node (function).
attach-child (function).
combine-siblings (function).
copy-node (function).
cut-parent (function).
link (function).
link-children (function).
node (structure).
node-children (reader).
(setf node-children) (writer).
node-data (reader).
(setf node-data) (writer).
node-key (reader).
(setf node-key) (writer).
node-p (function).
node-parent (reader).
(setf node-parent) (writer).
pair-children (function).
minheap/rank-pairing-heap.lispminheap (system).
clear-heap (function).
decrease-key (function).
empty-p (function).
extract-min (function).
extract-node (function).
heap-size (function).
insert (function).
meld (function).
peek-min (function).
print-object (method).
rank-pairing-heap (class).
%make-node (function).
attach-child (function).
copy-node (function).
cut-parent (function).
d-rank (function).
heap-size-access (reader method).
(setf heap-size-access) (writer method).
link (function).
link-fair (function).
link-unfair (function).
node (structure).
node-data (reader).
(setf node-data) (writer).
node-key (reader).
(setf node-key) (writer).
node-lchild (reader).
(setf node-lchild) (writer).
node-p (function).
node-parent (reader).
(setf node-parent) (writer).
node-rank (reader).
(setf node-rank) (writer).
node-rchild (reader).
(setf node-rchild) (writer).
minheap/rank-pairing-heap-clist.lispminheap (system).
clear-heap (function).
decrease-key (function).
empty-p (function).
extract-min (function).
extract-node (function).
heap-size (function).
insert (function).
meld (function).
peek-min (function).
print-object (method).
rank-pairing-heap-clist (class).
%make-node (function).
attach-child (function).
copy-node (function).
cut-parent (function).
d-rank (function).
insert-circular (function).
link-fair (function).
make-circular (function).
meld-circular (function).
node (structure).
node-data (reader).
(setf node-data) (writer).
node-key (reader).
(setf node-key) (writer).
node-lchild (reader).
(setf node-lchild) (writer).
node-p (function).
node-parent (reader).
(setf node-parent) (writer).
node-rank (reader).
(setf node-rank) (writer).
node-rchild (reader).
(setf node-rchild) (writer).
rootp (function).
minheap/splay-heap.lispminheap (system).
clear-heap (function).
empty-p (function).
extract-min (function).
extract-node (function).
heap-size (function).
insert (function).
node-find (function).
peek-min (function).
copy-splay-node (function).
make-splay-node (function).
segment< (function).
segment> (function).
splay-heap (class).
splay-node (structure).
splay-node-element (reader).
(setf splay-node-element) (writer).
splay-node-left (reader).
(setf splay-node-left) (writer).
splay-node-p (function).
splay-node-right (reader).
(setf splay-node-right) (writer).
splay-node-segment (reader).
(setf splay-node-segment) (writer).
splay-tree-delete (function).
splay-tree-insert (function).
splay-tree-splay (function).
minheap/violation-heap.lispminheap (system).
clear-heap (function).
decrease-key (function).
empty-p (function).
extract-min (function).
extract-node (function).
heap-size (function).
insert (function).
meld (function).
peek-min (function).
print-object (method).
violation-heap (class).
%make-node (function).
1st/2nd-child-p (function).
attach-next (function).
clean-p (function).
cleaning (function).
copy-node (function).
cut-child (function).
goodness (function).
join-lists (function).
link (function).
make-singular-list (function).
no-violation-p (function).
node (structure).
node-child (reader).
(setf node-child) (writer).
node-data (reader).
(setf node-data) (writer).
node-goodness (reader).
(setf node-goodness) (writer).
node-key (reader).
(setf node-key) (writer).
node-next (reader).
(setf node-next) (writer).
node-p (function).
node-prev (reader).
(setf node-prev) (writer).
node-rank (reader).
(setf node-rank) (writer).
root-p (function).
to-front (function).
unlink (function).
Packages are listed by definition order.
splay-heappairing-elmasribinary-heaprank-pairing-heap-clistrank-pairing-heapfib-heapviolation-heappairing-heap-listpairing-heapsplay-heapcommon-lisp.
clear-heap (function).
empty-p (function).
extract-min (function).
extract-node (function).
heap-size (function).
insert (function).
node-find (function).
peek-min (function).
copy-splay-node (function).
make-splay-node (function).
segment< (function).
segment> (function).
splay-heap (class).
splay-node (structure).
splay-node-element (reader).
(setf splay-node-element) (writer).
splay-node-left (reader).
(setf splay-node-left) (writer).
splay-node-p (function).
splay-node-right (reader).
(setf splay-node-right) (writer).
splay-node-segment (reader).
(setf splay-node-segment) (writer).
splay-tree-delete (function).
splay-tree-insert (function).
splay-tree-splay (function).
pairing-elmasricommon-lisp.
clear-heap (function).
decrease-key (function).
empty-p (function).
extract-min (function).
extract-node (function).
heap-size (function).
insert (function).
meld (function).
pairing-elmasri (class).
peek-min (function).
%make-node (function).
attach-child (function).
clean-up (function).
combine-siblings (function).
copy-node (function).
cut-parent (function).
delete-node-from-childseq (function).
link (function).
link-children (function).
node (structure).
node-data (reader).
(setf node-data) (writer).
node-key (reader).
(setf node-key) (writer).
node-lchild (reader).
(setf node-lchild) (writer).
node-p (function).
node-parent (reader).
(setf node-parent) (writer).
node-pooled (reader).
(setf node-pooled) (writer).
node-sibling (reader).
(setf node-sibling) (writer).
pair-children (function).
update-decrease (function).
update-min (function).
binary-heapcommon-lisp.
alist-to-heap (function).
binary-heap (class).
clear-heap (function).
decrease-key (function).
empty-p (function).
extract-min (function).
extract-node (function).
heap-size (function).
insert (function).
meld (function).
peek-min (function).
%make-node (function).
+initial-size+ (constant).
array-index (type).
bin-heap-array (generic reader).
(setf bin-heap-array) (generic writer).
copy-node (function).
left (function).
node (structure).
node-data (reader).
(setf node-data) (writer).
node-index (reader).
(setf node-index) (writer).
node-key (reader).
(setf node-key) (writer).
node-p (function).
parent (function).
perlocate-up (function).
right (function).
sink (function).
swap-nodes (function).
vector-to-heapvector (function).
rank-pairing-heap-clistcommon-lisp.
clear-heap (function).
decrease-key (function).
empty-p (function).
extract-min (function).
extract-node (function).
heap-size (function).
insert (function).
meld (function).
peek-min (function).
rank-pairing-heap-clist (class).
%make-node (function).
attach-child (function).
copy-node (function).
cut-parent (function).
d-rank (function).
insert-circular (function).
link-fair (function).
make-circular (function).
meld-circular (function).
node (structure).
node-data (reader).
(setf node-data) (writer).
node-key (reader).
(setf node-key) (writer).
node-lchild (reader).
(setf node-lchild) (writer).
node-p (function).
node-parent (reader).
(setf node-parent) (writer).
node-rank (reader).
(setf node-rank) (writer).
node-rchild (reader).
(setf node-rchild) (writer).
rootp (function).
rank-pairing-heapcommon-lisp.
clear-heap (function).
decrease-key (function).
empty-p (function).
extract-min (function).
extract-node (function).
heap-size (function).
insert (function).
meld (function).
peek-min (function).
rank-pairing-heap (class).
%make-node (function).
attach-child (function).
copy-node (function).
cut-parent (function).
d-rank (function).
heap-size-access (generic reader).
(setf heap-size-access) (generic writer).
link (function).
link-fair (function).
link-unfair (function).
node (structure).
node-data (reader).
(setf node-data) (writer).
node-key (reader).
(setf node-key) (writer).
node-lchild (reader).
(setf node-lchild) (writer).
node-p (function).
node-parent (reader).
(setf node-parent) (writer).
node-rank (reader).
(setf node-rank) (writer).
node-rchild (reader).
(setf node-rchild) (writer).
fib-heapcommon-lisp.
clear-heap (function).
decrease-key (function).
empty-p (function).
extract-min (function).
extract-node (function).
fib-heap (class).
heap-size (generic reader).
(setf heap-size) (generic writer).
insert (function).
meld (function).
peek-min (function).
%make-node (function).
cascading-cut (function).
consolidate (function).
copy-node (function).
cut (function).
link (function).
make-node (function).
min-node (generic reader).
(setf min-node) (generic writer).
node (structure).
node-child (reader).
(setf node-child) (writer).
node-data (reader).
(setf node-data) (writer).
node-degree (reader).
(setf node-degree) (writer).
node-key (reader).
(setf node-key) (writer).
node-left (reader).
(setf node-left) (writer).
node-mark (reader).
(setf node-mark) (writer).
node-p (function).
node-parent (reader).
(setf node-parent) (writer).
node-right (reader).
(setf node-right) (writer).
splice-lists (function).
violation-heapcommon-lisp.
clear-heap (function).
decrease-key (function).
empty-p (function).
extract-min (function).
extract-node (function).
heap-size (function).
insert (function).
meld (function).
peek-min (function).
violation-heap (class).
%make-node (function).
1st/2nd-child-p (function).
attach-next (function).
clean-p (function).
cleaning (function).
copy-node (function).
cut-child (function).
goodness (function).
join-lists (function).
link (function).
make-singular-list (function).
no-violation-p (function).
node (structure).
node-child (reader).
(setf node-child) (writer).
node-data (reader).
(setf node-data) (writer).
node-goodness (reader).
(setf node-goodness) (writer).
node-key (reader).
(setf node-key) (writer).
node-next (reader).
(setf node-next) (writer).
node-p (function).
node-prev (reader).
(setf node-prev) (writer).
node-rank (reader).
(setf node-rank) (writer).
root-p (function).
to-front (function).
unlink (function).
pairing-heap-listcommon-lisp.
clear-heap (function).
decrease-key (function).
empty-p (function).
extract-min (function).
extract-node (function).
heap-size (function).
insert (function).
meld (function).
pairing-heap (class).
peek-min (function).
%make-node (function).
attach-child (function).
combine-siblings (function).
copy-node (function).
cut-parent (function).
link (function).
link-children (function).
node (structure).
node-children (reader).
(setf node-children) (writer).
node-data (reader).
(setf node-data) (writer).
node-key (reader).
(setf node-key) (writer).
node-p (function).
node-parent (reader).
(setf node-parent) (writer).
pair-children (function).
pairing-heapcommon-lisp.
clear-heap (function).
decrease-key (function).
empty-p (function).
extract-min (function).
extract-node (function).
heap-size (function).
insert (function).
meld (function).
pairing-heap (class).
peek-min (function).
%make-node (function).
attach-child (function).
combine-siblings (function).
copy-node (function).
cut-parent (function).
delete-node-from-childseq (function).
link (function).
link-children (function).
node (structure).
node-data (reader).
(setf node-data) (writer).
node-key (reader).
(setf node-key) (writer).
node-lchild (reader).
(setf node-lchild) (writer).
node-p (function).
node-parent (reader).
(setf node-parent) (writer).
node-sibling (reader).
(setf node-sibling) (writer).
pair-children (function).
Definitions are sorted by export status, category, package, and then by lexicographic order.
Coerces an ALIST of (KEY . VALUE) conses into a heap.
Return NIL if HEAP is empty, otherwise the minnimal node.
Insert a new node with KEY and associated DATA item into the HEAP root-list. No consolidation is done at this time.
Melds HEAP-A and HEAP-B into HEAP-A and returns it. HEAP-A and HEAP-B may be modified and may have become empty after this operation.
Melds HEAP-A and HEAP-B into a new heap and returns it. HEAP-A is returned as new union of both heaps.
Melds HEAP-A and HEAP-B into HEAP-A and returns it. HEAP-B will be empty after this operation but may be used further.
Melds HEAP-A and HEAP-B into HEAP-A and returns it. HEAP-B will be empty after this operation but may be used further.
Melds HEAP-A and HEAP-B into a new heap and returns it. HEAP-A and HEAP-B will be empty after this operation but may be used further.
Melds HEAP-A and HEAP-B into HEAP-A and returns it. HEAP-B will be empty after this operation but may be used further.
Melds HEAP-A and HEAP-B into HEAP-A and returns it. HEAP-B will be empty after this operation but may be used further.
pairing-elmasri) stream) ¶binary-heap) stream) ¶rank-pairing-heap-clist) stream) ¶rank-pairing-heap) stream) ¶violation-heap) stream) ¶pairing-heap) stream) ¶pairing-heap) stream) ¶common-lisp.
(vector (or null binary-heap::node))
(make-array binary-heap::+initial-size+ :adjustable t :fill-pointer 0 :element-type (quote (or null binary-heap::node)) :initial-element nil)
:array
(integer 0 *)
0
:size
(or null pairing-elmasri::node)
:root
common-lisp.
(or null pairing-elmasri::node)
:min
list
:decreased
fixnum
0
:pooled
Returns the parent of NODE if NODE is a first or second child, NIL otherwise.
Remove X from the child list of Y.
Calculate new goodness value for NODE.
Insert NODE into circular LIST rooted at the minimum key. Return the expanded list, again rooted at the minimum key.
Destructively joins two circular node lists LIST-A and LIST-B returning the smaller of the two entry points as result.
Make node Y a child of node X.
Create a singleton circular list.
Return a new heap node with KEY and DATA as key/data items and set the cycle list accordingly.
Destructively melds two circular non-NIL lists. Each list must be rooted by the node element with minimum key.
data.
data.
data.
data.
data.
data.
data.
data.
left.
mark.
next.
prev.
rank.
rank.
rank.
left.
Splice two circular lists together
Puts NODE to the front of the circular list which has MIN as front element. Return NODE as new front element.
binary-heap)) ¶automatically generated reader method
binary-heap)) ¶automatically generated writer method
rank-pairing-heap)) ¶automatically generated reader method
size.
rank-pairing-heap)) ¶automatically generated writer method
size.
structure-object.
fixnum
0
boolean
(or null pairing-elmasri::node)
(or null pairing-elmasri::node)
(or null pairing-elmasri::node)
structure-object.
fixnum
0
(or null rank-pairing-heap-clist::node)
(or null rank-pairing-heap-clist::node)
(or null rank-pairing-heap-clist::node)
(integer 0 89)
0
structure-object.
fixnum
0
(or null rank-pairing-heap::node)
(or null rank-pairing-heap::node)
(or null rank-pairing-heap::node)
(integer 0 62)
0
structure-object.
fixnum
0
(or null fib-heap::node)
(or null fib-heap::node)
(or null fib-heap::node)
(or null fib-heap::node)
(integer 0 90)
0
boolean
structure-object.
fixnum
0
(or null violation-heap::node)
(or null violation-heap::node)
(or null violation-heap::node)
(integer 0 4611686018427387903)
0
(integer 0 4611686018427387903)
0
structure-object.
fixnum
0
(or null pairing-heap::node)
(or null pairing-heap::node)
(or null pairing-heap::node)
| Jump to: | %
(
1
A B C D E F G H I J L M N P R S T U V |
|---|
| Jump to: | %
(
1
A B C D E F G H I J L M N P R S T U V |
|---|
| Jump to: | +
A C D E G I K L M N P R S T |
|---|
| Jump to: | +
A C D E G I K L M N P R S T |
|---|
| Jump to: | A B C F M N P R S T V |
|---|
| Jump to: | A B C F M N P R S T V |
|---|