The minheap Reference Manual

Table of Contents

The minheap Reference Manual

This is the minheap Reference Manual, generated automatically by Declt version 3.0 "Montgomery Scott" on Mon Apr 19 17:05:05 2021 GMT+0.

1 Introduction

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)*

2 Systems

The main system appears first, followed by any subsystem dependency.

2.1 minheap

Maintainer

Stephan Frank <defclass@googlemail.com>

License

BSD, see LICENSE

Description

Various heap/priority queue data structures

Source

minheap.asd (file)

Components

• 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)

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.

3.1 Lisp

3.1.1 minheap.asd

Location

minheap.asd

Systems

minheap (system)

3.1.2 minheap/binary-heap.lisp

Parent

minheap (system)

Location

binary-heap.lisp

Packages

binary-heap

Exported Definitions

• 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)

Internal Definitions

• %make-node (function)
• +initial-size+ (constant)
• array-index (type)
• bin-heap-array (method)
• (setf bin-heap-array) (method)
• copy-node (function)
• left (function)
• node (structure)
• node-data (function)
• (setf node-data) (function)
• node-index (function)
• (setf node-index) (function)
• node-key (function)
• (setf node-key) (function)
• node-p (function)
• parent (function)
• perlocate-up (function)
• right (function)
• sink (function)
• swap-nodes (function)
• vector-to-heapvector (function)

3.1.3 minheap/fib-heap.lisp

Parent

minheap (system)

Location

fib-heap.lisp

Packages

fib-heap

Exported Definitions

• clear-heap (function)
• decrease-key (function)
• empty-p (function)
• extract-min (function)
• extract-node (function)
• fib-heap (class)
• heap-size (method)
• (setf heap-size) (method)
• insert (function)
• meld (function)
• peek-min (function)

Internal Definitions

• %make-node (function)
• cascading-cut (function)
• consolidate (function)
• copy-node (function)
• cut (function)
• link (function)
• make-node (function)
• min-node (method)
• (setf min-node) (method)
• node (structure)
• node-child (function)
• (setf node-child) (function)
• node-data (function)
• (setf node-data) (function)
• node-degree (function)
• (setf node-degree) (function)
• node-key (function)
• (setf node-key) (function)
• node-left (function)
• (setf node-left) (function)
• node-mark (function)
• (setf node-mark) (function)
• node-p (function)
• node-parent (function)
• (setf node-parent) (function)
• node-right (function)
• (setf node-right) (function)
• splice-lists (function)

3.1.4 minheap/pairing-heap-elmasri.lisp

Parent

minheap (system)

Location

pairing-heap-elmasri.lisp

Packages

pairing-elmasri

Exported Definitions

• 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)

Internal Definitions

• %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 (function)
• (setf node-data) (function)
• node-key (function)
• (setf node-key) (function)
• node-lchild (function)
• (setf node-lchild) (function)
• node-p (function)
• node-parent (function)
• (setf node-parent) (function)
• node-pooled (function)
• (setf node-pooled) (function)
• node-sibling (function)
• (setf node-sibling) (function)
• pair-children (function)
• update-decrease (function)
• update-min (function)

3.1.5 minheap/pairing-heap.lisp

Parent

minheap (system)

Location

pairing-heap.lisp

Packages

pairing-heap

Exported Definitions

• 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)

Internal Definitions

• %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 (function)
• (setf node-data) (function)
• node-key (function)
• (setf node-key) (function)
• node-lchild (function)
• (setf node-lchild) (function)
• node-p (function)
• node-parent (function)
• (setf node-parent) (function)
• node-sibling (function)
• (setf node-sibling) (function)
• pair-children (function)

3.1.6 minheap/pairing-heap-listbased.lisp

Parent

minheap (system)

Location

pairing-heap-listbased.lisp

Packages

pairing-heap-list

Exported Definitions

• 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)

Internal Definitions

• %make-node (function)
• attach-child (function)
• combine-siblings (function)
• copy-node (function)
• cut-parent (function)
• link (function)
• link-children (function)
• node (structure)
• node-children (function)
• (setf node-children) (function)
• node-data (function)
• (setf node-data) (function)
• node-key (function)
• (setf node-key) (function)
• node-p (function)
• node-parent (function)
• (setf node-parent) (function)
• pair-children (function)

3.1.7 minheap/rank-pairing-heap.lisp

Parent

minheap (system)

Location

rank-pairing-heap.lisp

Packages

rank-pairing-heap

Exported Definitions

• 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)

Internal Definitions

• %make-node (function)
• attach-child (function)
• copy-node (function)
• cut-parent (function)
• d-rank (function)
• heap-size-access (method)
• (setf heap-size-access) (method)
• link (function)
• link-fair (function)
• link-unfair (function)
• node (structure)
• node-data (function)
• (setf node-data) (function)
• node-key (function)
• (setf node-key) (function)
• node-lchild (function)
• (setf node-lchild) (function)
• node-p (function)
• node-parent (function)
• (setf node-parent) (function)
• node-rank (function)
• (setf node-rank) (function)
• node-rchild (function)
• (setf node-rchild) (function)

3.1.8 minheap/rank-pairing-heap-clist.lisp

Parent

minheap (system)

Location

rank-pairing-heap-clist.lisp

Packages

rank-pairing-heap-clist

Exported Definitions

• 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)

Internal Definitions

• %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 (function)
• (setf node-data) (function)
• node-key (function)
• (setf node-key) (function)
• node-lchild (function)
• (setf node-lchild) (function)
• node-p (function)
• node-parent (function)
• (setf node-parent) (function)
• node-rank (function)
• (setf node-rank) (function)
• node-rchild (function)
• (setf node-rchild) (function)
• rootp (function)

3.1.9 minheap/splay-heap.lisp

Parent

minheap (system)

Location

splay-heap.lisp

Packages

splay-heap

Exported Definitions

• clear-heap (function)
• empty-p (function)
• extract-min (function)
• extract-node (function)
• heap-size (function)
• insert (function)
• node-find (function)
• peek-min (function)

Internal Definitions

• copy-splay-node (function)
• make-splay-node (function)
• segment< (function)
• segment> (function)
• splay-heap (class)
• splay-node (structure)
• splay-node-element (function)
• (setf splay-node-element) (function)
• splay-node-left (function)
• (setf splay-node-left) (function)
• splay-node-p (function)
• splay-node-right (function)
• (setf splay-node-right) (function)
• splay-node-segment (function)
• (setf splay-node-segment) (function)
• splay-tree-delete (function)
• splay-tree-insert (function)
• splay-tree-splay (function)

3.1.10 minheap/violation-heap.lisp

Parent

minheap (system)

Location

violation-heap.lisp

Packages

violation-heap

Exported Definitions

• 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)

Internal Definitions

• %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 (function)
• (setf node-child) (function)
• node-data (function)
• (setf node-data) (function)
• node-goodness (function)
• (setf node-goodness) (function)
• node-key (function)
• (setf node-key) (function)
• node-next (function)
• (setf node-next) (function)
• node-p (function)
• node-prev (function)
• (setf node-prev) (function)
• node-rank (function)
• (setf node-rank) (function)
• root-p (function)
• to-front (function)
• unlink (function)

4 Packages

Packages are listed by definition order.

4.1 binary-heap

Source

binary-heap.lisp (file)

Use List

common-lisp

Exported Definitions

• 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)

Internal Definitions

• %make-node (function)
• +initial-size+ (constant)
• array-index (type)
• bin-heap-array (generic function)
• bin-heap-array (method)
• (setf bin-heap-array) (method)
• (setf bin-heap-array) (generic function)
• copy-node (function)
• left (function)
• node (structure)
• node-data (function)
• (setf node-data) (function)
• node-index (function)
• (setf node-index) (function)
• node-key (function)
• (setf node-key) (function)
• node-p (function)
• parent (function)
• perlocate-up (function)
• right (function)
• sink (function)
• swap-nodes (function)
• vector-to-heapvector (function)

4.2 fib-heap

Source

fib-heap.lisp (file)

Use List

common-lisp

Exported Definitions

• clear-heap (function)
• decrease-key (function)
• empty-p (function)
• extract-min (function)
• extract-node (function)
• fib-heap (class)
• heap-size (generic function)
• heap-size (method)
• (setf heap-size) (method)
• (setf heap-size) (generic function)
• insert (function)
• meld (function)
• peek-min (function)

Internal Definitions

• %make-node (function)
• cascading-cut (function)
• consolidate (function)
• copy-node (function)
• cut (function)
• link (function)
• make-node (function)
• min-node (generic function)
• min-node (method)
• (setf min-node) (method)
• (setf min-node) (generic function)
• node (structure)
• node-child (function)
• (setf node-child) (function)
• node-data (function)
• (setf node-data) (function)
• node-degree (function)
• (setf node-degree) (function)
• node-key (function)
• (setf node-key) (function)
• node-left (function)
• (setf node-left) (function)
• node-mark (function)
• (setf node-mark) (function)
• node-p (function)
• node-parent (function)
• (setf node-parent) (function)
• node-right (function)
• (setf node-right) (function)
• splice-lists (function)

4.3 pairing-elmasri

Source

pairing-heap-elmasri.lisp (file)

Use List

common-lisp

Exported Definitions

• 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)

Internal Definitions

• %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 (function)
• (setf node-data) (function)
• node-key (function)
• (setf node-key) (function)
• node-lchild (function)
• (setf node-lchild) (function)
• node-p (function)
• node-parent (function)
• (setf node-parent) (function)
• node-pooled (function)
• (setf node-pooled) (function)
• node-sibling (function)
• (setf node-sibling) (function)
• pair-children (function)
• update-decrease (function)
• update-min (function)

4.4 pairing-heap

Source

pairing-heap.lisp (file)

Use List

common-lisp

Exported Definitions

• 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)

Internal Definitions

• %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 (function)
• (setf node-data) (function)
• node-key (function)
• (setf node-key) (function)
• node-lchild (function)
• (setf node-lchild) (function)
• node-p (function)
• node-parent (function)
• (setf node-parent) (function)
• node-sibling (function)
• (setf node-sibling) (function)
• pair-children (function)

4.5 pairing-heap-list

Source

pairing-heap-listbased.lisp (file)

Use List

common-lisp

Exported Definitions

• 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)

Internal Definitions

• %make-node (function)
• attach-child (function)
• combine-siblings (function)
• copy-node (function)
• cut-parent (function)
• link (function)
• link-children (function)
• node (structure)
• node-children (function)
• (setf node-children) (function)
• node-data (function)
• (setf node-data) (function)
• node-key (function)
• (setf node-key) (function)
• node-p (function)
• node-parent (function)
• (setf node-parent) (function)
• pair-children (function)

4.6 rank-pairing-heap

Source

rank-pairing-heap.lisp (file)

Use List

common-lisp

Exported Definitions

• 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)

Internal Definitions

• %make-node (function)
• attach-child (function)
• copy-node (function)
• cut-parent (function)
• d-rank (function)
• heap-size-access (generic function)
• heap-size-access (method)
• (setf heap-size-access) (method)
• (setf heap-size-access) (generic function)
• link (function)
• link-fair (function)
• link-unfair (function)
• node (structure)
• node-data (function)
• (setf node-data) (function)
• node-key (function)
• (setf node-key) (function)
• node-lchild (function)
• (setf node-lchild) (function)
• node-p (function)
• node-parent (function)
• (setf node-parent) (function)
• node-rank (function)
• (setf node-rank) (function)
• node-rchild (function)
• (setf node-rchild) (function)

4.7 rank-pairing-heap-clist

Source

rank-pairing-heap-clist.lisp (file)

Use List

common-lisp

Exported Definitions

• 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)

Internal Definitions

• %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 (function)
• (setf node-data) (function)
• node-key (function)
• (setf node-key) (function)
• node-lchild (function)
• (setf node-lchild) (function)
• node-p (function)
• node-parent (function)
• (setf node-parent) (function)
• node-rank (function)
• (setf node-rank) (function)
• node-rchild (function)
• (setf node-rchild) (function)
• rootp (function)

4.8 splay-heap

Source

splay-heap.lisp (file)

Use List

common-lisp

Exported Definitions

• clear-heap (function)
• empty-p (function)
• extract-min (function)
• extract-node (function)
• heap-size (function)
• insert (function)
• node-find (function)
• peek-min (function)

Internal Definitions

• copy-splay-node (function)
• make-splay-node (function)
• segment< (function)
• segment> (function)
• splay-heap (class)
• splay-node (structure)
• splay-node-element (function)
• (setf splay-node-element) (function)
• splay-node-left (function)
• (setf splay-node-left) (function)
• splay-node-p (function)
• splay-node-right (function)
• (setf splay-node-right) (function)
• splay-node-segment (function)
• (setf splay-node-segment) (function)
• splay-tree-delete (function)
• splay-tree-insert (function)
• splay-tree-splay (function)

4.9 violation-heap

Source

violation-heap.lisp (file)

Use List

common-lisp

Exported Definitions

• 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)

Internal Definitions

• %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 (function)
• (setf node-child) (function)
• node-data (function)
• (setf node-data) (function)
• node-goodness (function)
• (setf node-goodness) (function)
• node-key (function)
• (setf node-key) (function)
• node-next (function)
• (setf node-next) (function)
• node-p (function)
• node-prev (function)
• (setf node-prev) (function)
• node-rank (function)
• (setf node-rank) (function)
• root-p (function)
• to-front (function)
• unlink (function)

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.

5.1 Exported definitions

5.1.1 Functions

Function: alist-to-heap ALIST

Coerces an ALIST of (KEY . VALUE) conses into a heap.

Package

binary-heap

Source

binary-heap.lisp (file)

Function: clear-heap HEAP

Package

binary-heap

Source

binary-heap.lisp (file)

Function: clear-heap HEAP

Package

fib-heap

Source

fib-heap.lisp (file)

Function: clear-heap HEAP

Package

pairing-elmasri

Source

pairing-heap-elmasri.lisp (file)

Function: clear-heap HEAP

Package

pairing-heap

Source

pairing-heap.lisp (file)

Function: clear-heap HEAP

Package

pairing-heap-list

Source

pairing-heap-listbased.lisp (file)

Function: clear-heap HEAP

Package

rank-pairing-heap

Source

rank-pairing-heap.lisp (file)

Function: clear-heap HEAP

Package

rank-pairing-heap-clist

Source

rank-pairing-heap-clist.lisp (file)

Function: clear-heap HEAP

Package

splay-heap

Source

splay-heap.lisp (file)

Function: clear-heap HEAP

Package

violation-heap

Source

violation-heap.lisp (file)

Function: decrease-key HEAP NODE KEY

Package

binary-heap

Source

binary-heap.lisp (file)

Function: decrease-key HEAP NODE KEY

Package

fib-heap

Source

fib-heap.lisp (file)

Function: decrease-key HEAP NODE KEY

Package

pairing-elmasri

Source

pairing-heap-elmasri.lisp (file)

Function: decrease-key HEAP NODE KEY

Package

pairing-heap

Source

pairing-heap.lisp (file)

Function: decrease-key HEAP NODE KEY

Package

pairing-heap-list

Source

pairing-heap-listbased.lisp (file)

Function: decrease-key HEAP NODE KEY

Package

rank-pairing-heap

Source

rank-pairing-heap.lisp (file)

Function: decrease-key HEAP NODE KEY

Package

rank-pairing-heap-clist

Source

rank-pairing-heap-clist.lisp (file)

Function: decrease-key HEAP NODE KEY

Package

violation-heap

Source

violation-heap.lisp (file)

Function: empty-p HEAP

Package

binary-heap

Source

binary-heap.lisp (file)

Function: empty-p HEAP

Return NIL if HEAP is empty, otherwise the minnimal node.

Package

fib-heap

Source

fib-heap.lisp (file)

Function: empty-p HEAP

Package

pairing-elmasri

Source

pairing-heap-elmasri.lisp (file)

Function: empty-p HEAP

Package

pairing-heap

Source

pairing-heap.lisp (file)

Function: empty-p HEAP

Package

pairing-heap-list

Source

pairing-heap-listbased.lisp (file)

Function: empty-p HEAP

Package

rank-pairing-heap

Source

rank-pairing-heap.lisp (file)

Function: empty-p HEAP

Package

rank-pairing-heap-clist

Source

rank-pairing-heap-clist.lisp (file)

Function: empty-p HEAP

Package

splay-heap

Source

splay-heap.lisp (file)

Function: empty-p HEAP

Package

violation-heap

Source

violation-heap.lisp (file)

Function: extract-min HEAP

Package

binary-heap

Source

binary-heap.lisp (file)

Function: extract-min HEAP

Package

fib-heap

Source

fib-heap.lisp (file)

Function: extract-min HEAP

Package

pairing-elmasri

Source

pairing-heap-elmasri.lisp (file)

Function: extract-min HEAP

Package

pairing-heap

Source

pairing-heap.lisp (file)

Function: extract-min HEAP

Package

pairing-heap-list

Source

pairing-heap-listbased.lisp (file)

Function: extract-min HEAP

Package

rank-pairing-heap

Source

rank-pairing-heap.lisp (file)

Function: extract-min HEAP

Package

rank-pairing-heap-clist

Source

rank-pairing-heap-clist.lisp (file)

Function: extract-min HEAP

Package

splay-heap

Source

splay-heap.lisp (file)

Function: extract-min HEAP

Package

violation-heap

Source

violation-heap.lisp (file)

Function: extract-node HEAP NODE

Package

binary-heap

Source

binary-heap.lisp (file)

Function: extract-node HEAP NODE

Package

fib-heap

Source

fib-heap.lisp (file)

Function: extract-node HEAP NODE

Package

pairing-elmasri

Source

pairing-heap-elmasri.lisp (file)

Function: extract-node HEAP NODE

Package

pairing-heap

Source

pairing-heap.lisp (file)

Function: extract-node HEAP NODE

Package

pairing-heap-list

Source

pairing-heap-listbased.lisp (file)

Function: extract-node HEAP NODE

Package

rank-pairing-heap

Source

rank-pairing-heap.lisp (file)

Function: extract-node HEAP NODE

Package

rank-pairing-heap-clist

Source

rank-pairing-heap-clist.lisp (file)

Function: extract-node HEAP KEY

Package

splay-heap

Source

splay-heap.lisp (file)

Function: extract-node HEAP NODE

Package

violation-heap

Source

violation-heap.lisp (file)

Function: heap-size HEAP

Package

binary-heap

Source

binary-heap.lisp (file)

Function: heap-size HEAP

Package

pairing-elmasri

Source

pairing-heap-elmasri.lisp (file)

Function: heap-size HEAP

Package

pairing-heap

Source

pairing-heap.lisp (file)

Function: heap-size HEAP

Package

pairing-heap-list

Source

pairing-heap-listbased.lisp (file)

Function: heap-size HEAP

Package

rank-pairing-heap

Source

rank-pairing-heap.lisp (file)

Function: heap-size HEAP

Package

rank-pairing-heap-clist

Source

rank-pairing-heap-clist.lisp (file)

Function: heap-size HEAP

Package

splay-heap

Source

splay-heap.lisp (file)

Function: heap-size HEAP

Package

violation-heap

Source

violation-heap.lisp (file)

Function: insert HEAP KEY DATA

Package

binary-heap

Source

binary-heap.lisp (file)

Function: insert HEAP KEY DATA

Insert a new node with KEY and associated DATA item into the HEAP root-list. No consolidation is done at this time.

Package

fib-heap

Source

fib-heap.lisp (file)

Function: insert HEAP KEY DATA

Package

pairing-elmasri

Source

pairing-heap-elmasri.lisp (file)

Function: insert HEAP KEY DATA

Package

pairing-heap

Source

pairing-heap.lisp (file)

Function: insert HEAP KEY DATA

Package

pairing-heap-list

Source

pairing-heap-listbased.lisp (file)

Function: insert HEAP KEY DATA

Package

rank-pairing-heap

Source

rank-pairing-heap.lisp (file)

Function: insert HEAP KEY DATA

Package

rank-pairing-heap-clist

Source

rank-pairing-heap-clist.lisp (file)

Function: insert HEAP KEY ITEM

Package

splay-heap

Source

splay-heap.lisp (file)

Function: insert HEAP KEY DATA

Package

violation-heap

Source

violation-heap.lisp (file)

Function: meld HEAP-A HEAP-B

Melds HEAP-A and HEAP-B into a new heap and returns it. HEAP-A is returned as new union of both heaps.

Package

binary-heap

Source

binary-heap.lisp (file)

Function: meld HEAP-A HEAP-B

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.

Package

fib-heap

Source

fib-heap.lisp (file)

Function: meld HEAP-A HEAP-B

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.

Package

pairing-elmasri

Source

pairing-heap-elmasri.lisp (file)

Function: meld HEAP-A HEAP-B

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.

Package

pairing-heap

Source

pairing-heap.lisp (file)

Function: meld HEAP-A HEAP-B

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.

Package

pairing-heap-list

Source

pairing-heap-listbased.lisp (file)

Function: meld HEAP-A HEAP-B

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.

Package

rank-pairing-heap

Source

rank-pairing-heap.lisp (file)

Function: meld HEAP-A HEAP-B

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.

Package

rank-pairing-heap-clist

Source

rank-pairing-heap-clist.lisp (file)

Function: meld HEAP-A HEAP-B

Package

violation-heap

Source

violation-heap.lisp (file)

Function: node-find HEAP KEY

Package

splay-heap

Source

splay-heap.lisp (file)

Function: peek-min HEAP

Package

binary-heap

Source

binary-heap.lisp (file)

Function: peek-min HEAP

Package

fib-heap

Source

fib-heap.lisp (file)

Function: peek-min HEAP

Package

pairing-elmasri

Source

pairing-heap-elmasri.lisp (file)

Function: peek-min HEAP

Package

pairing-heap

Source

pairing-heap.lisp (file)

Function: peek-min HEAP

Package

pairing-heap-list

Source

pairing-heap-listbased.lisp (file)

Function: peek-min HEAP

Package

rank-pairing-heap

Source

rank-pairing-heap.lisp (file)

Function: peek-min HEAP

Package

rank-pairing-heap-clist

Source

rank-pairing-heap-clist.lisp (file)

Function: peek-min HEAP

Package

splay-heap

Source

splay-heap.lisp (file)

Function: peek-min HEAP

Package

violation-heap

Source

violation-heap.lisp (file)

5.1.2 Generic functions

Generic Function: heap-size OBJECT

Generic Function: (setf heap-size) NEW-VALUE OBJECT

Package

fib-heap

Methods

Method: heap-size (FIB-HEAP fib-heap)

automatically generated reader method

Source

fib-heap.lisp (file)

Method: (setf heap-size) NEW-VALUE (FIB-HEAP fib-heap)

automatically generated writer method

Source

fib-heap.lisp (file)

5.1.3 Classes

Class: binary-heap ()

Package

binary-heap

Source

binary-heap.lisp (file)

Direct superclasses

standard-object (class)

Direct methods

• print-object (method)
• bin-heap-array (method)
• bin-heap-array (method)

Direct slots

Slot: array

Type

(vector (or null binary-heap::node))

Initargs

:array

Initform

(make-array binary-heap::+initial-size+ :adjustable t :fill-pointer 0 :element-type (quote (or null binary-heap::node)) :initial-element nil)

Readers

bin-heap-array (generic function)

Writers

(setf bin-heap-array) (generic function)

Class: fib-heap ()

Package

fib-heap

Source

fib-heap.lisp (file)

Direct superclasses

standard-object (class)

Direct methods

• print-object (method)
• heap-size (method)
• heap-size (method)
• min-node (method)
• min-node (method)

Direct slots

Slot: min

Type

(or null fib-heap::node)

Readers

min-node (generic function)

Writers

(setf min-node) (generic function)

Slot: nodes

Type

(integer 0 4611686018427387903)

Initform

0

Readers

heap-size (generic function)

Writers

(setf heap-size) (generic function)

Class: pairing-elmasri ()

Package

pairing-elmasri

Source

pairing-heap-elmasri.lisp (file)

Direct superclasses

standard-object (class)

Direct methods

print-object (method)

Direct slots

Slot: size

Type

(integer 0 *)

Initargs

:size

Initform

0

Slot: root

Type

(or null pairing-elmasri::node)

Initargs

:root

Slot: min

Type

(or null pairing-elmasri::node)

Initargs

:min

Slot: decreased

Type

list

Initargs

:decreased

Slot: pooled

Type

fixnum

Initargs

:pooled

Initform

0

Class: pairing-heap ()

Package

pairing-heap

Source

pairing-heap.lisp (file)

Direct superclasses

standard-object (class)

Direct methods

print-object (method)

Direct slots

Slot: size

Type

(integer 0 *)

Initargs

:size

Initform

0

Slot: root

Type

(or null pairing-heap::node)

Initargs

:root

Class: pairing-heap ()

Package

pairing-heap-list

Source

pairing-heap-listbased.lisp (file)

Direct superclasses

standard-object (class)

Direct methods

print-object (method)

Direct slots

Slot: size

Type

(integer 0 *)

Initargs

:size

Initform

0

Slot: root

Type

(or null pairing-heap-list::node)

Initargs

:root

Class: rank-pairing-heap ()

Package

rank-pairing-heap

Source

rank-pairing-heap.lisp (file)

Direct superclasses

standard-object (class)

Direct methods

• print-object (method)
• heap-size-access (method)
• heap-size-access (method)

Direct slots

Slot: size

Type

(integer 0 *)

Initargs

:size

Initform

0

Readers

heap-size-access (generic function)

Writers

(setf heap-size-access) (generic function)

Slot: root

Type

(or null rank-pairing-heap::node)

Initargs

:roots

Class: rank-pairing-heap-clist ()

Package

rank-pairing-heap-clist

Source

rank-pairing-heap-clist.lisp (file)

Direct superclasses

standard-object (class)

Direct methods

print-object (method)

Direct slots

Slot: size

Type

(integer 0 *)

Initargs

:size

Initform

0

Slot: roots

Type

list

Initargs

:roots

Class: violation-heap ()

Package

violation-heap

Source

violation-heap.lisp (file)

Direct superclasses

standard-object (class)

Direct methods

print-object (method)

Direct slots

Slot: size

Type

(integer 0 *)

Initargs

:size

Initform

0

Slot: rootlist

Type

(or null violation-heap::node)

Initargs

:rootlist

5.2 Internal definitions

5.2.1 Constants

Constant: +initial-size+

initial queue vector size

Package

binary-heap

Source

binary-heap.lisp (file)

5.2.2 Functions

Function: %make-node KEY DATA INDEX

Package

binary-heap

Source

binary-heap.lisp (file)

Function: %make-node KEY DATA

Package

fib-heap

Source

fib-heap.lisp (file)

Function: %make-node KEY DATA

Package

pairing-elmasri

Source

pairing-heap-elmasri.lisp (file)

Function: %make-node KEY DATA

Package

pairing-heap

Source

pairing-heap.lisp (file)

Function: %make-node KEY DATA

Package

pairing-heap-list

Source

pairing-heap-listbased.lisp (file)

Function: %make-node KEY DATA

Package

rank-pairing-heap

Source

rank-pairing-heap.lisp (file)

Function: %make-node KEY DATA

Package

rank-pairing-heap-clist

Source

rank-pairing-heap-clist.lisp (file)

Function: %make-node KEY DATA

Package

violation-heap

Source

violation-heap.lisp (file)

Function: 1st/2nd-child-p NODE

Returns the parent of NODE if NODE is a first or second child, NIL otherwise.

Package

violation-heap

Source

violation-heap.lisp (file)

Function: attach-child PARENT CHILD

Package

pairing-elmasri

Source

pairing-heap-elmasri.lisp (file)

Function: attach-child PARENT CHILD

Package

pairing-heap

Source

pairing-heap.lisp (file)

Function: attach-child PARENT CHILD

Package

pairing-heap-list

Source

pairing-heap-listbased.lisp (file)

Function: attach-child PARENT CHILD

Package

rank-pairing-heap

Source

rank-pairing-heap.lisp (file)

Function: attach-child PARENT CHILD

Package

rank-pairing-heap-clist

Source

rank-pairing-heap-clist.lisp (file)

Function: attach-next NODE NEXT-NODE

Package

violation-heap

Source

violation-heap.lisp (file)

Function: cascading-cut ()

Package

fib-heap

Source

fib-heap.lisp (file)

Function: clean-p ()

Package

violation-heap

Source

violation-heap.lisp (file)

Function: clean-up HEAP

Package

pairing-elmasri

Source

pairing-heap-elmasri.lisp (file)

Function: cleaning ()

Package

violation-heap

Source

violation-heap.lisp (file)

Function: combine-siblings PARENT

Package

pairing-elmasri

Source

pairing-heap-elmasri.lisp (file)

Function: combine-siblings PARENT

Package

pairing-heap

Source

pairing-heap.lisp (file)

Function: combine-siblings PARENT

Package

pairing-heap-list

Source

pairing-heap-listbased.lisp (file)

Function: consolidate ()

Package

fib-heap

Source

fib-heap.lisp (file)

Function: copy-node INSTANCE

Package

binary-heap

Source

binary-heap.lisp (file)

Function: copy-node INSTANCE

Package

fib-heap

Source

fib-heap.lisp (file)

Function: copy-node INSTANCE

Package

pairing-elmasri

Source

pairing-heap-elmasri.lisp (file)

Function: copy-node INSTANCE

Package

pairing-heap

Source

pairing-heap.lisp (file)

Function: copy-node INSTANCE

Package

pairing-heap-list

Source

pairing-heap-listbased.lisp (file)

Function: copy-node INSTANCE

Package

rank-pairing-heap

Source

rank-pairing-heap.lisp (file)

Function: copy-node INSTANCE

Package

rank-pairing-heap-clist

Source

rank-pairing-heap-clist.lisp (file)

Function: copy-node INSTANCE

Package

violation-heap

Source

violation-heap.lisp (file)

Function: copy-splay-node INSTANCE

Package

splay-heap

Source

splay-heap.lisp (file)

Function: cut ()

Remove X from the child list of Y.

Package

fib-heap

Source

fib-heap.lisp (file)

Function: cut-child ()

Package

violation-heap

Source

violation-heap.lisp (file)

Function: cut-parent NODE

Package

pairing-elmasri

Source

pairing-heap-elmasri.lisp (file)

Function: cut-parent NODE

Package

pairing-heap

Source

pairing-heap.lisp (file)

Function: cut-parent NODE

Package

pairing-heap-list

Source

pairing-heap-listbased.lisp (file)

Function: cut-parent NODE

Package

rank-pairing-heap

Source

rank-pairing-heap.lisp (file)

Function: cut-parent NODE

Package

rank-pairing-heap-clist

Source

rank-pairing-heap-clist.lisp (file)

Function: d-rank NODE

Package

rank-pairing-heap

Source

rank-pairing-heap.lisp (file)

Function: d-rank NODE

Package

rank-pairing-heap-clist

Source

rank-pairing-heap-clist.lisp (file)

Function: delete-node-from-childseq NODE FIRST-CHILD &optional REPLACE

Package

pairing-elmasri

Source

pairing-heap-elmasri.lisp (file)

Function: delete-node-from-childseq NODE FIRST-CHILD

Package

pairing-heap

Source

pairing-heap.lisp (file)

Function: goodness NODE

Calculate new goodness value for NODE.

Package

violation-heap

Source

violation-heap.lisp (file)

Function: insert-circular LIST NODE

Insert NODE into circular LIST rooted at the minimum key. Return the expanded list, again rooted at the minimum key.

Package

rank-pairing-heap-clist

Source

rank-pairing-heap-clist.lisp (file)

Function: join-lists LIST-A LIST-B

Destructively joins two circular node lists LIST-A and LIST-B returning the smaller of the two entry points as result.

Package

violation-heap

Source

violation-heap.lisp (file)

Function: left K

Package

binary-heap

Source

binary-heap.lisp (file)

Function: link ()

Make node Y a child of node X.

Package

fib-heap

Source

fib-heap.lisp (file)

Function: link NODE-A NODE-B

Package

pairing-elmasri

Source

pairing-heap-elmasri.lisp (file)

Function: link NODE-A NODE-B

Package

pairing-heap

Source

pairing-heap.lisp (file)

Function: link NODE-A NODE-B

Package

pairing-heap-list

Source

pairing-heap-listbased.lisp (file)

Function: link NODE-A NODE-B

Package

rank-pairing-heap

Source

rank-pairing-heap.lisp (file)

Function: link ()

Package

violation-heap

Source

violation-heap.lisp (file)

Function: link-children PARENT

Package

pairing-elmasri

Source

pairing-heap-elmasri.lisp (file)

Function: link-children PARENT

Package

pairing-heap

Source

pairing-heap.lisp (file)

Function: link-children PARENT

Package

pairing-heap-list

Source

pairing-heap-listbased.lisp (file)

Function: link-fair NODE-A NODE-B

Package

rank-pairing-heap

Source

rank-pairing-heap.lisp (file)

Function: link-fair NODE-A NODE-B

Package

rank-pairing-heap-clist

Source

rank-pairing-heap-clist.lisp (file)

Function: link-unfair NODE-A NODE-B

Package

rank-pairing-heap

Source

rank-pairing-heap.lisp (file)

Function: make-circular NODE

Create a singleton circular list.

Package

rank-pairing-heap-clist

Source

rank-pairing-heap-clist.lisp (file)

Function: make-node KEY DATA

Return a new heap node with KEY and DATA as key/data items and set the cycle list accordingly.

Package

fib-heap

Source

fib-heap.lisp (file)

Function: make-singular-list NODE

Package

violation-heap

Source

violation-heap.lisp (file)

Function: make-splay-node &key (SEGMENT SEGMENT) (ELEMENT ELEMENT) (LEFT LEFT) (RIGHT RIGHT)

Package

splay-heap

Source

splay-heap.lisp (file)

Function: meld-circular LIST-A LIST-B

Destructively melds two circular non-NIL lists. Each list must be rooted by the node element with minimum key.

Package

rank-pairing-heap-clist

Source

rank-pairing-heap-clist.lisp (file)

Function: no-violation-p NODE

Package

violation-heap

Source

violation-heap.lisp (file)

Function: node-child INSTANCE

Function: (setf node-child) VALUE INSTANCE

Package

fib-heap

Source

fib-heap.lisp (file)

Function: node-child INSTANCE

Function: (setf node-child) VALUE INSTANCE

Package

violation-heap

Source

violation-heap.lisp (file)

Function: node-children INSTANCE

Function: (setf node-children) VALUE INSTANCE

Package

pairing-heap-list

Source

pairing-heap-listbased.lisp (file)

Function: node-data INSTANCE

Function: (setf node-data) VALUE INSTANCE

Package

binary-heap

Source

binary-heap.lisp (file)

Function: node-data INSTANCE

Function: (setf node-data) VALUE INSTANCE

Package

fib-heap

Source

fib-heap.lisp (file)

Function: node-data INSTANCE

Function: (setf node-data) VALUE INSTANCE

Package

pairing-elmasri

Source

pairing-heap-elmasri.lisp (file)

Function: node-data INSTANCE

Function: (setf node-data) VALUE INSTANCE

Package

pairing-heap

Source

pairing-heap.lisp (file)

Function: node-data INSTANCE

Function: (setf node-data) VALUE INSTANCE

Package

pairing-heap-list

Source

pairing-heap-listbased.lisp (file)

Function: node-data INSTANCE

Function: (setf node-data) VALUE INSTANCE

Package

rank-pairing-heap

Source

rank-pairing-heap.lisp (file)

Function: node-data INSTANCE

Function: (setf node-data) VALUE INSTANCE

Package

rank-pairing-heap-clist

Source

rank-pairing-heap-clist.lisp (file)

Function: node-data INSTANCE

Function: (setf node-data) VALUE INSTANCE

Package

violation-heap

Source

violation-heap.lisp (file)

Function: node-degree INSTANCE

Function: (setf node-degree) VALUE INSTANCE

Package

fib-heap

Source

fib-heap.lisp (file)

Function: node-goodness INSTANCE

Function: (setf node-goodness) VALUE INSTANCE

Package

violation-heap

Source

violation-heap.lisp (file)

Function: node-index INSTANCE

Function: (setf node-index) VALUE INSTANCE

Package

binary-heap

Source

binary-heap.lisp (file)

Function: node-key INSTANCE

Function: (setf node-key) VALUE INSTANCE

Package

binary-heap

Source

binary-heap.lisp (file)

Function: node-key INSTANCE

Function: (setf node-key) VALUE INSTANCE

Package

fib-heap

Source

fib-heap.lisp (file)

Function: node-key INSTANCE

Function: (setf node-key) VALUE INSTANCE

Package

pairing-elmasri

Source

pairing-heap-elmasri.lisp (file)

Function: node-key INSTANCE

Function: (setf node-key) VALUE INSTANCE

Package

pairing-heap

Source

pairing-heap.lisp (file)

Function: node-key INSTANCE

Function: (setf node-key) VALUE INSTANCE

Package

pairing-heap-list

Source

pairing-heap-listbased.lisp (file)

Function: node-key INSTANCE

Function: (setf node-key) VALUE INSTANCE

Package

rank-pairing-heap

Source

rank-pairing-heap.lisp (file)

Function: node-key INSTANCE

Function: (setf node-key) VALUE INSTANCE

Package

rank-pairing-heap-clist

Source

rank-pairing-heap-clist.lisp (file)

Function: node-key INSTANCE

Function: (setf node-key) VALUE INSTANCE

Package

violation-heap

Source

violation-heap.lisp (file)

Function: node-lchild INSTANCE

Function: (setf node-lchild) VALUE INSTANCE

Package

pairing-elmasri

Source

pairing-heap-elmasri.lisp (file)

Function: node-lchild INSTANCE

Function: (setf node-lchild) VALUE INSTANCE

Package

pairing-heap

Source

pairing-heap.lisp (file)

Function: node-lchild INSTANCE

Function: (setf node-lchild) VALUE INSTANCE

Package

rank-pairing-heap

Source

rank-pairing-heap.lisp (file)

Function: node-lchild INSTANCE

Function: (setf node-lchild) VALUE INSTANCE

Package

rank-pairing-heap-clist

Source

rank-pairing-heap-clist.lisp (file)

Function: node-left INSTANCE

Function: (setf node-left) VALUE INSTANCE

Package

fib-heap

Source

fib-heap.lisp (file)

Function: node-mark INSTANCE

Function: (setf node-mark) VALUE INSTANCE

Package

fib-heap

Source

fib-heap.lisp (file)

Function: node-next INSTANCE

Function: (setf node-next) VALUE INSTANCE

Package

violation-heap

Source

violation-heap.lisp (file)

Function: node-p OBJECT

Package

binary-heap

Source

binary-heap.lisp (file)

Function: node-p OBJECT

Package

fib-heap

Source

fib-heap.lisp (file)

Function: node-p OBJECT

Package

pairing-elmasri

Source

pairing-heap-elmasri.lisp (file)

Function: node-p OBJECT

Package

pairing-heap

Source

pairing-heap.lisp (file)

Function: node-p OBJECT

Package

pairing-heap-list

Source

pairing-heap-listbased.lisp (file)

Function: node-p OBJECT

Package

rank-pairing-heap

Source

rank-pairing-heap.lisp (file)

Function: node-p OBJECT

Package

rank-pairing-heap-clist

Source

rank-pairing-heap-clist.lisp (file)

Function: node-p OBJECT

Package

violation-heap

Source

violation-heap.lisp (file)

Function: node-parent INSTANCE

Function: (setf node-parent) VALUE INSTANCE

Package

fib-heap

Source

fib-heap.lisp (file)

Function: node-parent INSTANCE

Function: (setf node-parent) VALUE INSTANCE

Package

pairing-elmasri

Source

pairing-heap-elmasri.lisp (file)

Function: node-parent INSTANCE

Function: (setf node-parent) VALUE INSTANCE

Package

pairing-heap

Source

pairing-heap.lisp (file)

Function: node-parent INSTANCE

Function: (setf node-parent) VALUE INSTANCE

Package

pairing-heap-list

Source

pairing-heap-listbased.lisp (file)

Function: node-parent INSTANCE

Function: (setf node-parent) VALUE INSTANCE

Package

rank-pairing-heap

Source

rank-pairing-heap.lisp (file)

Function: node-parent INSTANCE

Function: (setf node-parent) VALUE INSTANCE

Package

rank-pairing-heap-clist

Source

rank-pairing-heap-clist.lisp (file)

Function: node-pooled INSTANCE

Function: (setf node-pooled) VALUE INSTANCE

Package

pairing-elmasri

Source

pairing-heap-elmasri.lisp (file)

Function: node-prev INSTANCE

Function: (setf node-prev) VALUE INSTANCE

Package

violation-heap

Source

violation-heap.lisp (file)

Function: node-rank INSTANCE

Function: (setf node-rank) VALUE INSTANCE

Package

rank-pairing-heap

Source

rank-pairing-heap.lisp (file)

Function: node-rank INSTANCE

Function: (setf node-rank) VALUE INSTANCE

Package

rank-pairing-heap-clist

Source

rank-pairing-heap-clist.lisp (file)

Function: node-rank INSTANCE

Function: (setf node-rank) VALUE INSTANCE

Package

violation-heap

Source

violation-heap.lisp (file)

Function: node-rchild INSTANCE

Function: (setf node-rchild) VALUE INSTANCE

Package

rank-pairing-heap

Source

rank-pairing-heap.lisp (file)

Function: node-rchild INSTANCE

Function: (setf node-rchild) VALUE INSTANCE

Package

rank-pairing-heap-clist

Source

rank-pairing-heap-clist.lisp (file)

Function: node-right INSTANCE

Function: (setf node-right) VALUE INSTANCE

Package

fib-heap

Source

fib-heap.lisp (file)