Next: Introduction, Previous: (dir), Up: (dir) [Contents][Index]
This is the minheap Reference Manual, generated automatically by Declt version 3.0 "Montgomery Scott" on Thu Mar 11 14:12:53 2021 GMT+0.
• Introduction | What minheap is all about | |
• Systems | The systems documentation | |
• Files | The files documentation | |
• Packages | The packages documentation | |
• Definitions | The symbols documentation | |
• Indexes | Concepts, functions, variables and data types |
This project contains several heap data structures with priority queue and melding functionality. The heaps are hard-wired to min-heap only functionality on fixnum keys as I needed maximum performance for this use case. Since key comparison is in general limited to one or two places for every data structure variant only, an extension/re-use for max-heap functionality should be trivial. Implemented heap data structures and their properties are collected in the table below. Executive summary: for almost all cases the 'pairing heap' should give you the best performance. The 'rank pairing heap' has slightly worse overall performance but better worst case behaviour. The different heap data structures posess the following computational complexities (amortized complexity is annotated with a '*'): binary heap: - insert O(lg n) - find/peek min O(1) - delete min O(lg n) - delete node O(lg n) - decrease key O(lg n) - meld O(lg n) splay heap: - insert O(lg n)* - find/peek min O(lg n)* - delete min O(lg n)* - delete node O(lg n)* - decrease key N/A - meld N/A fibonacci heap: - insert O(1)* - find/peek min O(1)* - delete min O(lg n)* - delete node O(lg n)* - decrease key O(1)* - meld O(1)* pairing heap and variants: - insert O(1)* - find/peek min O(1)* - delete min O(lg n)* - delete node O(lg n)* - decrease key O(1)* - meld O(1)* violation heap: - insert O(1)* - find/peek min O(1)* - delete min O(lg n)* - delete node O(lg n)* - decrease key O(1)* - meld O(1)*
Next: Files, Previous: Introduction, Up: Top [Contents][Index]
The main system appears first, followed by any subsystem dependency.
• The minheap system |
Stephan Frank <defclass@googlemail.com>
BSD, see LICENSE
Various heap/priority queue data structures
minheap.asd (file)
Files are sorted by type and then listed depth-first from the systems components trees.
• Lisp files |
Next: The minheap/binary-heap․lisp file, Previous: Lisp files, Up: Lisp files [Contents][Index]
minheap.asd
minheap (system)
Next: The minheap/fib-heap․lisp file, Previous: The minheap․asd file, Up: Lisp files [Contents][Index]
minheap (system)
binary-heap.lisp
Next: The minheap/pairing-heap-elmasri․lisp file, Previous: The minheap/binary-heap․lisp file, Up: Lisp files [Contents][Index]
minheap (system)
fib-heap.lisp
Next: The minheap/pairing-heap․lisp file, Previous: The minheap/fib-heap․lisp file, Up: Lisp files [Contents][Index]
minheap (system)
pairing-heap-elmasri.lisp
Next: The minheap/pairing-heap-listbased․lisp file, Previous: The minheap/pairing-heap-elmasri․lisp file, Up: Lisp files [Contents][Index]
minheap (system)
pairing-heap.lisp
Next: The minheap/rank-pairing-heap․lisp file, Previous: The minheap/pairing-heap․lisp file, Up: Lisp files [Contents][Index]
minheap (system)
pairing-heap-listbased.lisp
Next: The minheap/rank-pairing-heap-clist․lisp file, Previous: The minheap/pairing-heap-listbased․lisp file, Up: Lisp files [Contents][Index]
minheap (system)
rank-pairing-heap.lisp
Next: The minheap/splay-heap․lisp file, Previous: The minheap/rank-pairing-heap․lisp file, Up: Lisp files [Contents][Index]
minheap (system)
rank-pairing-heap-clist.lisp
Next: The minheap/violation-heap․lisp file, Previous: The minheap/rank-pairing-heap-clist․lisp file, Up: Lisp files [Contents][Index]
minheap (system)
splay-heap.lisp
Previous: The minheap/splay-heap․lisp file, Up: Lisp files [Contents][Index]
minheap (system)
violation-heap.lisp
Next: Definitions, Previous: Files, Up: Top [Contents][Index]
Packages are listed by definition order.
Next: The fib-heap package, Previous: Packages, Up: Packages [Contents][Index]
binary-heap.lisp (file)
common-lisp
Next: The pairing-elmasri package, Previous: The binary-heap package, Up: Packages [Contents][Index]
fib-heap.lisp (file)
common-lisp
Next: The pairing-heap package, Previous: The fib-heap package, Up: Packages [Contents][Index]
pairing-heap-elmasri.lisp (file)
common-lisp
Next: The pairing-heap-list package, Previous: The pairing-elmasri package, Up: Packages [Contents][Index]
pairing-heap.lisp (file)
common-lisp
Next: The rank-pairing-heap package, Previous: The pairing-heap package, Up: Packages [Contents][Index]
pairing-heap-listbased.lisp (file)
common-lisp
Next: The rank-pairing-heap-clist package, Previous: The pairing-heap-list package, Up: Packages [Contents][Index]
rank-pairing-heap.lisp (file)
common-lisp
Next: The splay-heap package, Previous: The rank-pairing-heap package, Up: Packages [Contents][Index]
rank-pairing-heap-clist.lisp (file)
common-lisp
Next: The violation-heap package, Previous: The rank-pairing-heap-clist package, Up: Packages [Contents][Index]
splay-heap.lisp (file)
common-lisp
Previous: The splay-heap package, Up: Packages [Contents][Index]
violation-heap.lisp (file)
common-lisp
Definitions are sorted by export status, category, package, and then by lexicographic order.
• Exported definitions | ||
• Internal definitions |
Next: Internal definitions, Previous: Definitions, Up: Definitions [Contents][Index]
• Exported functions | ||
• Exported generic functions | ||
• Exported classes |
Next: Exported generic functions, Previous: Exported definitions, Up: Exported definitions [Contents][Index]
Coerces an ALIST of (KEY . VALUE) conses into a heap.
binary-heap.lisp (file)
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)
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)
violation-heap.lisp (file)
binary-heap.lisp (file)
Return NIL if HEAP is empty, otherwise the minnimal node.
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)
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)
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)
binary-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)
binary-heap.lisp (file)
Insert a new node with KEY and associated DATA item into the HEAP root-list. No consolidation is done at this time.
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)
Melds HEAP-A and HEAP-B into a new heap and returns it. HEAP-A is returned as new union of both heaps.
binary-heap.lisp (file)
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.
fib-heap.lisp (file)
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.
pairing-heap-elmasri.lisp (file)
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-heap.lisp (file)
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-heap-listbased.lisp (file)
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.
rank-pairing-heap.lisp (file)
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.
rank-pairing-heap-clist.lisp (file)
violation-heap.lisp (file)
splay-heap.lisp (file)
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)
Next: Exported classes, Previous: Exported functions, Up: Exported definitions [Contents][Index]
automatically generated reader method
fib-heap.lisp (file)
automatically generated writer method
fib-heap.lisp (file)
Previous: Exported generic functions, Up: Exported definitions [Contents][Index]
binary-heap.lisp (file)
standard-object (class)
(vector (or null binary-heap::node))
:array
(make-array binary-heap::+initial-size+ :adjustable t :fill-pointer 0 :element-type (quote (or null binary-heap::node)) :initial-element nil)
bin-heap-array (generic function)
(setf bin-heap-array) (generic function)
fib-heap.lisp (file)
standard-object (class)
(or null fib-heap::node)
min-node (generic function)
(setf min-node) (generic function)
(integer 0 4611686018427387903)
0
heap-size (generic function)
(setf heap-size) (generic function)
pairing-heap-elmasri.lisp (file)
standard-object (class)
print-object (method)
(integer 0 *)
:size
0
(or null pairing-elmasri::node)
:root
(or null pairing-elmasri::node)
:min
list
:decreased
fixnum
:pooled
0
pairing-heap.lisp (file)
standard-object (class)
print-object (method)
(integer 0 *)
:size
0
(or null pairing-heap::node)
:root
pairing-heap-listbased.lisp (file)
standard-object (class)
print-object (method)
(integer 0 *)
:size
0
(or null pairing-heap-list::node)
:root
rank-pairing-heap.lisp (file)
standard-object (class)
(integer 0 *)
:size
0
heap-size-access (generic function)
(setf heap-size-access) (generic function)
(or null rank-pairing-heap::node)
:roots
rank-pairing-heap-clist.lisp (file)
standard-object (class)
print-object (method)
(integer 0 *)
:size
0
list
:roots
violation-heap.lisp (file)
standard-object (class)
print-object (method)
(integer 0 *)
:size
0
(or null violation-heap::node)
:rootlist
Previous: Exported definitions, Up: Definitions [Contents][Index]
• Internal constants | ||
• Internal functions | ||
• Internal generic functions | ||
• Internal structures | ||
• Internal classes | ||
• Internal types |
Next: Internal functions, Previous: Internal definitions, Up: Internal definitions [Contents][Index]
initial queue vector size
binary-heap.lisp (file)
Next: Internal generic functions, Previous: Internal constants, Up: Internal definitions [Contents][Index]
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)
violation-heap.lisp (file)
Returns the parent of NODE if NODE is a first or second child, NIL otherwise.
violation-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)
violation-heap.lisp (file)
fib-heap.lisp (file)
violation-heap.lisp (file)
pairing-heap-elmasri.lisp (file)
violation-heap.lisp (file)
pairing-heap-elmasri.lisp (file)
pairing-heap.lisp (file)
pairing-heap-listbased.lisp (file)
fib-heap.lisp (file)
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)
violation-heap.lisp (file)
splay-heap.lisp (file)
Remove X from the child list of Y.
fib-heap.lisp (file)
violation-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)
rank-pairing-heap.lisp (file)
rank-pairing-heap-clist.lisp (file)
pairing-heap-elmasri.lisp (file)
pairing-heap.lisp (file)
Calculate new goodness value for NODE.
violation-heap.lisp (file)
Insert NODE into circular LIST rooted at the minimum key. Return the expanded list, again rooted at the minimum key.
rank-pairing-heap-clist.lisp (file)
Destructively joins two circular node lists LIST-A and LIST-B returning the smaller of the two entry points as result.
violation-heap.lisp (file)
binary-heap.lisp (file)
Make node Y a child of node X.
fib-heap.lisp (file)
pairing-heap-elmasri.lisp (file)
pairing-heap.lisp (file)
pairing-heap-listbased.lisp (file)
rank-pairing-heap.lisp (file)
violation-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)
rank-pairing-heap.lisp (file)
Create a singleton circular list.
rank-pairing-heap-clist.lisp (file)
Return a new heap node with KEY and DATA as key/data items and set the cycle list accordingly.
fib-heap.lisp (file)
violation-heap.lisp (file)
splay-heap.lisp (file)
Destructively melds two circular non-NIL lists. Each list must be rooted by the node element with minimum key.
rank-pairing-heap-clist.lisp (file)
violation-heap.lisp (file)
fib-heap.lisp (file)
violation-heap.lisp (file)
pairing-heap-listbased.lisp (file)
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)
violation-heap.lisp (file)
fib-heap.lisp (file)
violation-heap.lisp (file)
binary-heap.lisp (file)
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)
violation-heap.lisp (file)
pairing-heap-elmasri.lisp (file)
pairing-heap.lisp (file)
rank-pairing-heap.lisp (file)
rank-pairing-heap-clist.lisp (file)
fib-heap.lisp (file)
fib-heap.lisp (file)
violation-heap.lisp (file)
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)
violation-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)
pairing-heap-elmasri.lisp (file)
violation-heap.lisp (file)
rank-pairing-heap.lisp (file)
rank-pairing-heap-clist.lisp (file)
violation-heap.lisp (file)
rank-pairing-heap.lisp (file)
rank-pairing-heap-clist.lisp (file)
fib-heap.lisp (file)
pairing-heap-elmasri.lisp (file)
pairing-heap.lisp (file)
pairing-heap-elmasri.lisp (file)
pairing-heap.lisp (file)
pairing-heap-listbased.lisp (file)
binary-heap.lisp (file)
binary-heap.lisp (file)
binary-heap.lisp (file)
violation-heap.lisp (file)
rank-pairing-heap-clist.lisp (file)
splay-heap.lisp (file)
splay-heap.lisp (file)
binary-heap.lisp (file)
splay-heap.lisp (file)
splay-heap.lisp (file)
splay-heap.lisp (file)
splay-heap.lisp (file)
splay-heap.lisp (file)
splay-heap.lisp (file)
splay-heap.lisp (file)
splay-heap.lisp (file)
Splice two circular lists together
fib-heap.lisp (file)
binary-heap.lisp (file)
Puts NODE to the front of the circular list which has MIN as front element. Return NODE as new front element.
violation-heap.lisp (file)
violation-heap.lisp (file)
pairing-heap-elmasri.lisp (file)
pairing-heap-elmasri.lisp (file)
binary-heap.lisp (file)
Next: Internal structures, Previous: Internal functions, Up: Internal definitions [Contents][Index]
automatically generated reader method
binary-heap.lisp (file)
automatically generated writer method
binary-heap.lisp (file)
automatically generated reader method
rank-pairing-heap.lisp (file)
automatically generated writer method
rank-pairing-heap.lisp (file)
automatically generated reader method
fib-heap.lisp (file)
automatically generated writer method
fib-heap.lisp (file)
Next: Internal classes, Previous: Internal generic functions, Up: Internal definitions [Contents][Index]
binary-heap.lisp (file)
structure-object (structure)
fixnum
0
node-key (function)
(setf node-key) (function)
binary-heap::array-index
0
node-index (function)
(setf node-index) (function)
node-data (function)
(setf node-data) (function)
fib-heap.lisp (file)
structure-object (structure)
print-object (method)
fixnum
0
node-key (function)
(setf node-key) (function)
node-data (function)
(setf node-data) (function)
(or null fib-heap::node)
node-parent (function)
(setf node-parent) (function)
(or null fib-heap::node)
node-child (function)
(setf node-child) (function)
(or null fib-heap::node)
node-left (function)
(setf node-left) (function)
(or null fib-heap::node)
node-right (function)
(setf node-right) (function)
(integer 0 90)
0
node-degree (function)
(setf node-degree) (function)
boolean
node-mark (function)
(setf node-mark) (function)
pairing-heap-elmasri.lisp (file)
structure-object (structure)
fixnum
0
node-key (function)
(setf node-key) (function)
node-data (function)
(setf node-data) (function)
boolean
node-pooled (function)
(setf node-pooled) (function)
(or null pairing-elmasri::node)
node-lchild (function)
(setf node-lchild) (function)
(or null pairing-elmasri::node)
node-sibling (function)
(setf node-sibling) (function)
(or null pairing-elmasri::node)
node-parent (function)
(setf node-parent) (function)
pairing-heap.lisp (file)
structure-object (structure)
fixnum
0
node-key (function)
(setf node-key) (function)
node-data (function)
(setf node-data) (function)
(or null pairing-heap::node)
node-lchild (function)
(setf node-lchild) (function)
(or null pairing-heap::node)
node-sibling (function)
(setf node-sibling) (function)
(or null pairing-heap::node)
node-parent (function)
(setf node-parent) (function)
pairing-heap-listbased.lisp (file)
structure-object (structure)
fixnum
0
node-key (function)
(setf node-key) (function)
node-data (function)
(setf node-data) (function)
list
node-children (function)
(setf node-children) (function)
(or null pairing-heap-list::node)
node-parent (function)
(setf node-parent) (function)
rank-pairing-heap.lisp (file)
structure-object (structure)
fixnum
0
node-key (function)
(setf node-key) (function)
node-data (function)
(setf node-data) (function)
(or null rank-pairing-heap::node)
node-lchild (function)
(setf node-lchild) (function)
(or null rank-pairing-heap::node)
node-rchild (function)
(setf node-rchild) (function)
(or null rank-pairing-heap::node)
node-parent (function)
(setf node-parent) (function)
(integer 0 62)
0
node-rank (function)
(setf node-rank) (function)
rank-pairing-heap-clist.lisp (file)
structure-object (structure)
fixnum
0
node-key (function)
(setf node-key) (function)
node-data (function)
(setf node-data) (function)
(or null rank-pairing-heap-clist::node)
node-lchild (function)
(setf node-lchild) (function)
(or null rank-pairing-heap-clist::node)
node-rchild (function)
(setf node-rchild) (function)
(or null rank-pairing-heap-clist::node)
node-parent (function)
(setf node-parent) (function)
(integer 0 89)
0
node-rank (function)
(setf node-rank) (function)
violation-heap.lisp (file)
structure-object (structure)
fixnum
0
node-key (function)
(setf node-key) (function)
node-data (function)
(setf node-data) (function)
(or null violation-heap::node)
node-prev (function)
(setf node-prev) (function)
(or null violation-heap::node)
node-next (function)
(setf node-next) (function)
(or null violation-heap::node)
node-child (function)
(setf node-child) (function)
(integer 0 4611686018427387903)
0
node-rank (function)
(setf node-rank) (function)
(integer 0 4611686018427387903)
0
node-goodness (function)
(setf node-goodness) (function)
splay-heap.lisp (file)
structure-object (structure)
(or fixnum null)
splay-node-segment (function)
(setf splay-node-segment) (function)
splay-node-element (function)
(setf splay-node-element) (function)
(or null splay-heap::splay-node)
splay-node-left (function)
(setf splay-node-left) (function)
(or null splay-heap::splay-node)
splay-node-right (function)
(setf splay-node-right) (function)
Next: Internal types, Previous: Internal structures, Up: Internal definitions [Contents][Index]
splay-heap.lisp (file)
standard-object (class)
(or splay-heap::splay-node null)
fixnum
0
Previous: Internal classes, Up: Internal definitions [Contents][Index]
binary-heap.lisp (file)
Previous: Definitions, Up: Top [Contents][Index]
• Concept index | ||
• Function index | ||
• Variable index | ||
• Data type index |
Next: Function index, Previous: Indexes, Up: Indexes [Contents][Index]
Jump to: | F L M |
---|
Jump to: | F L M |
---|
Next: Variable index, Previous: Concept index, Up: Indexes [Contents][Index]
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 |
---|
Next: Data type index, Previous: Function index, Up: Indexes [Contents][Index]
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 |
---|
Previous: Variable index, Up: Indexes [Contents][Index]
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 |
---|