Next: Introduction, Previous: (dir), Up: (dir) [Contents][Index]
This is the binomialheap Reference Manual, generated automatically by Declt version 4.0 beta 2 "William Riker" on Mon Aug 15 03:16:42 2022 GMT+0.
Next: Systems, Previous: The binomialheap Reference Manual, Up: The binomialheap Reference Manual [Contents][Index]
___ __ __ ____ _ __ ___ __ _ _ ____ ___ ____
 .\ _\ \\ \/\ _\ \   ___ _\ __\ \  . \
 .<_ / \ .  \ / . \ _____\ _  ]_ . \ __/
___// /\_/___//v\// /\_/___/ / /___//\_//
Binomialheap is a compact and succint implementation of the binomial heap data structure in Common Lisp programming language. Insertion, extremum access, extremum extraction, and union operations are performed in O(logn) time.
(defvar *list* (loop repeat 20 collect (random 100)))
; => (25 50 12 53 53 55 41 71 71 41 33 8 71 57 28 4 89 96 58 25)
(defvar *heap* (makeinstance 'bh:binomialheap :test #'<))
; => #<BINOMIALHEAP {1002C4EC31}>
(dolist (item *list*)
(insertkey *heap* item))
; => NIL
(bh::printtree (bh::headof *heap*))
; => > ( 2) 25
; > ( 1) 89
; > ( 0) 96
; > ( 0) 58
; > ( 4) 4
; > ( 3) 12
; > ( 2) 41
; > ( 1) 53
; > ( 0) 55
; > ( 0) 71
; > ( 1) 25
; > ( 0) 50
; > ( 0) 53
; > ( 2) 8
; > ( 1) 41
; > ( 0) 71
; > ( 0) 33
; > ( 1) 57
; > ( 0) 71
; > ( 0) 28
; NIL
(bh:getextremumkey *heap*)
; => 4
(loop for x in (sort (copylist *list*) (testof *heap*))
for y = (extractextremumkey *heap*)
unless (= x y)
collect (cons x y))
; => NIL
(let ((h1 (makeinstance 'bh:binomialheap :test #'string<))
(h2 (makeinstance 'bh:binomialheap :test #'string<))
(l1 '("foo" "bar" "baz" "mov" "mov"))
(l2 '("i" "see" "dead" "binomial" "trees")))
(dolist (l l1) (bh:insertkey h1 l))
(bh::printtree (bh::headof h1))
; => > ( 0) "mov"
; > ( 2) "bar"
; > ( 1) "baz"
; > ( 0) "mov"
; > ( 0) "foo"
; NIL
(dolist (l l2) (bh:insertkey h2 l))
(bh::printtree (bh::headof h2))
; => > ( 0) "trees"
; > ( 2) "binomial"
; > ( 1) "i"
; > ( 0) "see"
; > ( 0) "dead"
; NIL
(let ((h3 (bh:uniteheaps h1 h2)))
(bh::printtree (bh::headof h3))))
; => > ( 1) "mov"
; > ( 0) "trees"
; > ( 3) "bar"
; > ( 2) "binomial"
; > ( 1) "i"
; > ( 0) "see"
; > ( 0) "dead"
; > ( 1) "baz"
; > ( 0) "mov"
; > ( 0) "foo"
; NIL
Despite binomial heaps are known to perform decrease/increase key and delete operations in O(logn) time, this is practically not that easy to implement. (For the rest of this talk, I'll skip the deletion operation because of it can be achieved through setting the key field of a node to the absolute extremum  i.e. negative infinity  and extracting the extremum.) Consider below example.
> [ Z ] >
^


> [ X ] >
^^^

++
++ ... 
  
> [ W0 ] > [ W1 ] > ... > [ WN ]
Suppose you decreased the key field of X and you need to bubble up X by swapping nodes in upwards direction appropriately. Because of random access is not possible in heap data structures, you need to figure out your own way of accessing to nodes  in this example consider you have the pointers in advance to the every BINOMIALTREE
in the BINOMIALHEAP
. There are two ways to swap nodes:
If you just swap the key fields of the nodes
(rotatef (keyof x) (keyof z))
everything will be fine, except that the pointers to the nodes that lost their original key fields will get invalidated. Now you cannot guarantee the validity of your node pointers and hence cannot issue any more decrease key operations.
If you swap the two node instances, your pointers won't get invalidated but this time you'll need to update the sibling and parent pointers as well,
(setf (parentof w0) z
(parentof w1) z
...
(parentof wn) z)
which will make your O(logn) complexity dreams fade away. (Moreover, you'll need to traverse sibling lists at levels of nodes X
and Y
to be able to find previous siblings to X
and Y
if you are not using doublylinkedlists. But even this scheme doesn't save us from the traversal of W1
, ..., WN
nodes.)
So how can we manage to perform decrease key operation in O(logn) time without invalidating any node pointers? The solution I come up with to this problem is as follows.
We can keep a separate hash table for the pointers to the nodes. When a node's key field gets modified, related hash table entry will get modified as well. And instead of returning to the user the actual BINOMIALTREE
instances, we'll return to the user the key of the related hash table entry. (Consider this hash table as a mapping between the hash table keys and the pointer to the actual node instance.)
Sounds too hairy? I think so. I'd be appreciated for any sort of enlightenment of a better solution.
Next: Modules, Previous: Introduction, Up: The binomialheap Reference Manual [Contents][Index]
The main system appears first, followed by any subsystem dependency.
A compact binomial heap implementation.
Volkan YAZICI <volkan.yazici@gmail.com>
BSD
src (module).
Next: Files, Previous: Systems, Up: The binomialheap Reference Manual [Contents][Index]
Modules are listed depthfirst from the system components tree.
binomialheap (system).
Next: Packages, Previous: Modules, Up: The binomialheap Reference Manual [Contents][Index]
Files are sorted by type and then listed depthfirst from the systems components trees.
Next: binomialheap/src/packages.lisp, Previous: Lisp, Up: Lisp [Contents][Index]
binomialheap (system).
Next: binomialheap/src/specials.lisp, Previous: binomialheap/binomialheap.asd, Up: Lisp [Contents][Index]
src (module).
Next: binomialheap/src/utils.lisp, Previous: binomialheap/src/packages.lisp, Up: Lisp [Contents][Index]
packages.lisp (file).
src (module).
Next: binomialheap/src/operations.lisp, Previous: binomialheap/src/specials.lisp, Up: Lisp [Contents][Index]
specials.lisp (file).
src (module).
Previous: binomialheap/src/utils.lisp, Up: Lisp [Contents][Index]
utils.lisp (file).
src (module).
Next: Definitions, Previous: Files, Up: The binomialheap Reference Manual [Contents][Index]
Packages are listed by definition order.
Next: binomialheapsystem, Previous: Packages, Up: Packages [Contents][Index]
bh
commonlisp.
Previous: binomialheap, Up: Packages [Contents][Index]
Next: Indexes, Previous: Packages, Up: The binomialheap Reference Manual [Contents][Index]
Definitions are sorted by export status, category, package, and then by lexicographic order.
Next: Internals, Previous: Definitions, Up: Definitions [Contents][Index]
Next: Generic functions, Previous: Public Interface, Up: Public Interface [Contents][Index]
Extracts the extremum value from the ‘BINOMIALHEAP’ pointed by ‘HEAP’. Function returns the ‘KEY’ field of the extracted ‘BINOMIALTREE’ instance.
Finds the ‘BINOMIALTREE’ with the extremum value and its ‘KEY’ field. Function returns ‘NIL’ in case of no items found.
Creates a new ‘BINOMIALTREE’ for ‘KEY’ and inserts this node to the ‘BINOMIALHEAP’ pointed by ‘HEAP’. Function returns the ‘KEY’.
Unites given two heaps of type ‘BINOMIALHEAP’ into a single one. (Assuming ‘TEST’ functions of each heap are equivalent.)
Next: Standalone methods, Previous: Ordinary functions, Up: Public Interface [Contents][Index]
automatically generated reader method
test.
automatically generated writer method
test.
Next: Classes, Previous: Generic functions, Up: Public Interface [Contents][Index]
Previous: Standalone methods, Up: Public Interface [Contents][Index]
Binomial heap container.
Previous: Public Interface, Up: Definitions [Contents][Index]
Next: Ordinary functions, Previous: Internals, Up: Internals [Contents][Index]
Next: Generic functions, Previous: Macros, Up: Internals [Contents][Index]
Finds the ‘BINOMIALTREE’ prior to the extremum in the sibling list pointed by ‘HEAD’. Function returns ‘NIL’ in case of no extremum or extremum at the beginning.
Constructs ‘SIBLING’ slots of given list of ‘BINOMIALTREE’s to provide given order.
Makes ‘X’ the child of ‘Y’.
Merges given two ‘BINOMIALTREE’s and their related siblings into a single ‘BINOMIALTREE’ sibling list.
Utility function to print binomial tree in a humanreadable(?) format.
Converts supplied ‘SEXP’ of ‘(KEY &KEY SIBLING CHILD)’ form into appropriate ‘BINOMIALTREE’ instance.
Returns reversed list of child and its consequent siblings of supplied ‘TREE’ of type ‘BINOMIALTREE’.
Converts supplied ‘BINOMIALTREE’ into ‘(KEY &KEY SIBLING CHILD)’ compound form.
Unites given ‘X’ and ‘Y’ ‘BINOMIALTREE’s and their related siblings into a single ‘BINOMIALTREE’.
Identical to ‘UNITEROOTLISTS’ except that this function doesn’t handle Case 2 condition and break the loop in Case 1. (Case 1 & 2 are redundant while adding a single node to a root list.)
Next: Classes, Previous: Ordinary functions, Up: Internals [Contents][Index]
automatically generated reader method
automatically generated writer method
automatically generated reader method
automatically generated writer method
automatically generated reader method
head.
automatically generated writer method
head.
automatically generated reader method
key.
automatically generated writer method
key.
automatically generated reader method
automatically generated writer method
automatically generated reader method
automatically generated writer method
Previous: Generic functions, Up: Internals [Contents][Index]
Binomial tree container.
binomialheap::binomialtree
:parent
(integer 0 *)
0
:degree
binomialheap::binomialtree
:child
binomialheap::binomialtree
:sibling
:key
Previous: Definitions, Up: The binomialheap Reference Manual [Contents][Index]
Jump to:  (
C D E F G H I K L M P S T U W 

Jump to:  (
C D E F G H I K L M P S T U W 

Next: Data types, Previous: Functions, Up: Indexes [Contents][Index]
Jump to:  C D H K P S T 

Jump to:  C D H K P S T 

Jump to:  B C F M O P S U 

Jump to:  B C F M O P S U 
