The binomial-heap Reference Manual

Table of Contents

Next: , Previous: , Up: (dir)   [Contents][Index]

The binomial-heap Reference Manual

This is the binomial-heap Reference Manual, generated automatically by Declt version 2.3 "Robert April" on Wed Mar 14 02:58:20 2018 GMT+0.


Next: , Previous: , Up: Top   [Contents][Index]

1 Introduction

___  __ __   ____ _    __ ___  __        _  _ ____ ___  ____
| .\ |_\| \|\|   ||\/\ |_\|  \ | |   ___ ||_|\| __\|  \ | . \
| .<_| /|  \|| . ||   \| /| . \| |__|___\| _ ||  ]_| . \| __/
|___/|/ |/\_/|___/|/v\/|/ |/\_/|___/     |/ |/|___/|/\_/|/

Abstract

Binomial-heap 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.

Demo

(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* (make-instance 'bh:binomial-heap :test #'<))
; => #<BINOMIAL-HEAP {1002C4EC31}>

(dolist (item *list*)
  (insert-key *heap* item))
; => NIL

(bh::print-tree (bh::head-of *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:get-extremum-key *heap*)
; => 4

(loop for x in (sort (copy-list *list*) (test-of *heap*))
      for y = (extract-extremum-key *heap*)
      unless (= x y)
      collect (cons x y))
; => NIL

(let ((h1 (make-instance 'bh:binomial-heap :test #'string<))
      (h2 (make-instance 'bh:binomial-heap :test #'string<))
      (l1 '("foo" "bar" "baz" "mov" "mov"))
      (l2 '("i" "see" "dead" "binomial" "trees")))
  (dolist (l l1) (bh:insert-key h1 l))
  (bh::print-tree (bh::head-of h1))
; => -> ( 0) "mov"
;    -> ( 2) "bar"
;      -> ( 1) "baz"
;        -> ( 0) "mov"
;      -> ( 0) "foo"
; NIL
  (dolist (l l2) (bh:insert-key h2 l))
  (bh::print-tree (bh::head-of h2))
; => -> ( 0) "trees"
;    -> ( 2) "binomial"
;      -> ( 1) "i"
;        -> ( 0) "see"
;      -> ( 0) "dead"
; NIL
  (let ((h3 (bh:unite-heaps h1 h2)))
    (bh::print-tree (bh::head-of h3))))
; => -> ( 1) "mov"
;      -> ( 0) "trees"
;    -> ( 3) "bar"
;      -> ( 2) "binomial"
;        -> ( 1) "i"
;          -> ( 0) "see"
;        -> ( 0) "dead"
;      -> ( 1) "baz"
;        -> ( 0) "mov"
;      -> ( 0) "foo"
; NIL

Caveats

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 BINOMIAL-TREE in the BINOMIAL-HEAP. There are two ways to swap nodes:

Swapping Key Fields

If you just swap the key fields of the nodes

(rotatef (key-of x) (key-of 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.

Swapping Node Instances

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 (parent-of w0) z
      (parent-of w1) z
...
(parent-of 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 doubly-linked-lists. But even this scheme doesn't save us from the traversal of W1, ..., WN nodes.)

Solution

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 BINOMIAL-TREE 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: , Previous: , Up: Top   [Contents][Index]

2 Systems

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


Previous: , Up: Systems   [Contents][Index]

2.1 binomial-heap

Author

Volkan YAZICI <volkan.yazici@gmail.com>

License

BSD

Description

A compact binomial heap implementation.

Source

binomial-heap.asd (file)

Component

src (module)


Next: , Previous: , Up: Top   [Contents][Index]

3 Modules

Modules are listed depth-first from the system components tree.


Previous: , Up: Modules   [Contents][Index]

3.1 binomial-heap/src

Parent

binomial-heap (system)

Location

src/

Components

Next: , Previous: , Up: Top   [Contents][Index]

4 Files

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


Previous: , Up: Files   [Contents][Index]

4.1 Lisp


Next: , Previous: , Up: Lisp files   [Contents][Index]

4.1.1 binomial-heap.asd

Location

binomial-heap.asd

Systems

binomial-heap (system)

Packages

binomial-heap-system


Next: , Previous: , Up: Lisp files   [Contents][Index]

4.1.2 binomial-heap/src/packages.lisp

Parent

src (module)

Location

src/packages.lisp

Packages

binomial-heap


Next: , Previous: , Up: Lisp files   [Contents][Index]

4.1.3 binomial-heap/src/specials.lisp

Dependency

packages.lisp (file)

Parent

src (module)

Location

src/specials.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

4.1.4 binomial-heap/src/utils.lisp

Dependency

specials.lisp (file)

Parent

src (module)

Location

src/utils.lisp

Internal Definitions

Previous: , Up: Lisp files   [Contents][Index]

4.1.5 binomial-heap/src/operations.lisp

Dependency

utils.lisp (file)

Parent

src (module)

Location

src/operations.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

5 Packages

Packages are listed by definition order.


Next: , Previous: , Up: Packages   [Contents][Index]

5.1 binomial-heap-system

Source

binomial-heap.asd

Use List

Previous: , Up: Packages   [Contents][Index]

5.2 binomial-heap

Source

packages.lisp (file)

Nickname

bh

Use List

common-lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

6 Definitions

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


Next: , Previous: , Up: Definitions   [Contents][Index]

6.1 Exported definitions


Next: , Previous: , Up: Exported definitions   [Contents][Index]

6.1.1 Functions

Function: extract-extremum-key HEAP

Extracts the extremum value from the ‘BINOMIAL-HEAP’ pointed by ‘HEAP’. Function returns the ‘KEY’ field of the extracted ‘BINOMIAL-TREE’ instance.

Package

binomial-heap

Source

operations.lisp (file)

Function: get-extremum-key HEAP

Finds the ‘BINOMIAL-TREE’ with the extremum value and its ‘KEY’ field. Function returns ‘NIL’ in case of no items found.

Package

binomial-heap

Source

operations.lisp (file)

Function: insert-key HEAP KEY

Creates a new ‘BINOMIAL-TREE’ for ‘KEY’ and inserts this node to the ‘BINOMIAL-HEAP’ pointed by ‘HEAP’. Function returns the ‘KEY’.

Package

binomial-heap

Source

operations.lisp (file)

Function: unite-heaps X Y

Unites given two heaps of type ‘BINOMIAL-HEAP’ into a single one. (Assuming ‘TEST’ functions of each heap are equivalent.)

Package

binomial-heap

Source

operations.lisp (file)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

6.1.2 Generic functions

Generic Function: test-of OBJECT
Generic Function: (setf test-of) NEW-VALUE OBJECT
Package

binomial-heap

Methods
Method: test-of (BINOMIAL-HEAP binomial-heap)

automatically generated reader method

Source

specials.lisp (file)

Method: (setf test-of) NEW-VALUE (BINOMIAL-HEAP binomial-heap)

automatically generated writer method

Source

specials.lisp (file)


Previous: , Up: Exported definitions   [Contents][Index]

6.1.3 Classes

Class: binomial-heap ()

Binomial heap container.

Package

binomial-heap

Source

specials.lisp (file)

Direct superclasses

standard-object (class)

Direct methods
Direct slots
Slot: head
Type

list

Initargs

:head

Readers

head-of (generic function)

Writers

(setf head-of) (generic function)

Slot: test
Type

function

Initargs

:test

Readers

test-of (generic function)

Writers

(setf test-of) (generic function)


Previous: , Up: Definitions   [Contents][Index]

6.2 Internal definitions


Next: , Previous: , Up: Internal definitions   [Contents][Index]

6.2.1 Macros

Macro: prog1-let (VAR VAL) &body BODY
Package

binomial-heap

Source

utils.lisp (file)

Macro: when-let (VAR VAL) &body BODY
Package

binomial-heap

Source

utils.lisp (file)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

6.2.2 Functions

Function: get-prior-to-extremum HEAD TEST

Finds the ‘BINOMIAL-TREE’ prior to the extremum in the sibling list pointed by ‘HEAD’. Function returns ‘NIL’ in case of no extremum or extremum at the beginning.

Package

binomial-heap

Source

operations.lisp (file)

Function: link-siblings TREES

Constructs ‘SIBLING’ slots of given list of ‘BINOMIAL-TREE’s to provide given order.

Package

binomial-heap

Source

operations.lisp (file)

Function: link-trees X Y

Makes ‘X’ the child of ‘Y’.

Package

binomial-heap

Source

operations.lisp (file)

Function: merge-siblings X Y

Merges given two ‘BINOMIAL-TREE’s and their related siblings into a single ‘BINOMIAL-TREE’ sibling list.

Package

binomial-heap

Source

operations.lisp (file)

Function: print-tree X

Utility function to print binomial tree in a human-readable(?) format.

Package

binomial-heap

Source

operations.lisp (file)

Function: sexp->tree SEXP

Converts supplied ‘SEXP’ of ‘(KEY &KEY SIBLING CHILD)’ form into appropriate ‘BINOMIAL-TREE’ instance.

Package

binomial-heap

Source

operations.lisp (file)

Function: sibling-list TREE

Returns reversed list of child and its consequent siblings of supplied ‘TREE’ of type ‘BINOMIAL-TREE’.

Package

binomial-heap

Source

operations.lisp (file)

Function: tree->sexp TREE

Converts supplied ‘BINOMIAL-TREE’ into ‘(KEY &KEY SIBLING CHILD)’ compound form.

Package

binomial-heap

Source

operations.lisp (file)

Function: unite-root-lists TEST X Y

Unites given ‘X’ and ‘Y’ ‘BINOMIAL-TREE’s and their related siblings into a single ‘BINOMIAL-TREE’.

Package

binomial-heap

Source

operations.lisp (file)

Function: unsafe-unite-root-lists TEST X Y

Identical to ‘UNITE-ROOT-LISTS’ 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.)

Package

binomial-heap

Source

operations.lisp (file)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

6.2.3 Generic functions

Generic Function: child-of OBJECT
Generic Function: (setf child-of) NEW-VALUE OBJECT
Package

binomial-heap

Methods
Method: child-of (BINOMIAL-TREE binomial-tree)

automatically generated reader method

Source

specials.lisp (file)

Method: (setf child-of) NEW-VALUE (BINOMIAL-TREE binomial-tree)

automatically generated writer method

Source

specials.lisp (file)

Generic Function: degree-of OBJECT
Generic Function: (setf degree-of) NEW-VALUE OBJECT
Package

binomial-heap

Methods
Method: degree-of (BINOMIAL-TREE binomial-tree)

automatically generated reader method

Source

specials.lisp (file)

Method: (setf degree-of) NEW-VALUE (BINOMIAL-TREE binomial-tree)

automatically generated writer method

Source

specials.lisp (file)

Generic Function: head-of OBJECT
Generic Function: (setf head-of) NEW-VALUE OBJECT
Package

binomial-heap

Methods
Method: head-of (BINOMIAL-HEAP binomial-heap)

automatically generated reader method

Source

specials.lisp (file)

Method: (setf head-of) NEW-VALUE (BINOMIAL-HEAP binomial-heap)

automatically generated writer method

Source

specials.lisp (file)

Generic Function: key-of OBJECT
Generic Function: (setf key-of) NEW-VALUE OBJECT
Package

binomial-heap

Methods
Method: key-of (BINOMIAL-TREE binomial-tree)

automatically generated reader method

Source

specials.lisp (file)

Method: (setf key-of) NEW-VALUE (BINOMIAL-TREE binomial-tree)

automatically generated writer method

Source

specials.lisp (file)

Generic Function: parent-of OBJECT
Generic Function: (setf parent-of) NEW-VALUE OBJECT
Package

binomial-heap

Methods
Method: parent-of (BINOMIAL-TREE binomial-tree)

automatically generated reader method

Source

specials.lisp (file)

Method: (setf parent-of) NEW-VALUE (BINOMIAL-TREE binomial-tree)

automatically generated writer method

Source

specials.lisp (file)

Generic Function: sibling-of OBJECT
Generic Function: (setf sibling-of) NEW-VALUE OBJECT
Package

binomial-heap

Methods
Method: sibling-of (BINOMIAL-TREE binomial-tree)

automatically generated reader method

Source

specials.lisp (file)

Method: (setf sibling-of) NEW-VALUE (BINOMIAL-TREE binomial-tree)

automatically generated writer method

Source

specials.lisp (file)


Previous: , Up: Internal definitions   [Contents][Index]

6.2.4 Classes

Class: binomial-tree ()

Binomial tree container.

Package

binomial-heap

Source

specials.lisp (file)

Direct superclasses

standard-object (class)

Direct methods
Direct slots
Slot: parent
Type

binomial-heap::binomial-tree

Initargs

:parent

Readers

parent-of (generic function)

Writers

(setf parent-of) (generic function)

Slot: degree
Type

(integer 0 *)

Initargs

:degree

Initform

0

Readers

degree-of (generic function)

Writers

(setf degree-of) (generic function)

Slot: child
Type

binomial-heap::binomial-tree

Initargs

:child

Readers

child-of (generic function)

Writers

(setf child-of) (generic function)

Slot: sibling
Type

binomial-heap::binomial-tree

Initargs

:sibling

Readers

sibling-of (generic function)

Writers

(setf sibling-of) (generic function)

Slot: key
Initargs

:key

Readers

key-of (generic function)

Writers

(setf key-of) (generic function)


Previous: , Up: Top   [Contents][Index]

Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts

Jump to:   B   F   L   M  
Index Entry  Section

B
binomial-heap.asd: The binomial-heap<dot>asd file
binomial-heap/src: The binomial-heap/src module
binomial-heap/src/operations.lisp: The binomial-heap/src/operations<dot>lisp file
binomial-heap/src/packages.lisp: The binomial-heap/src/packages<dot>lisp file
binomial-heap/src/specials.lisp: The binomial-heap/src/specials<dot>lisp file
binomial-heap/src/utils.lisp: The binomial-heap/src/utils<dot>lisp file

F
File, Lisp, binomial-heap.asd: The binomial-heap<dot>asd file
File, Lisp, binomial-heap/src/operations.lisp: The binomial-heap/src/operations<dot>lisp file
File, Lisp, binomial-heap/src/packages.lisp: The binomial-heap/src/packages<dot>lisp file
File, Lisp, binomial-heap/src/specials.lisp: The binomial-heap/src/specials<dot>lisp file
File, Lisp, binomial-heap/src/utils.lisp: The binomial-heap/src/utils<dot>lisp file

L
Lisp File, binomial-heap.asd: The binomial-heap<dot>asd file
Lisp File, binomial-heap/src/operations.lisp: The binomial-heap/src/operations<dot>lisp file
Lisp File, binomial-heap/src/packages.lisp: The binomial-heap/src/packages<dot>lisp file
Lisp File, binomial-heap/src/specials.lisp: The binomial-heap/src/specials<dot>lisp file
Lisp File, binomial-heap/src/utils.lisp: The binomial-heap/src/utils<dot>lisp file

M
Module, binomial-heap/src: The binomial-heap/src module

Jump to:   B   F   L   M  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.2 Functions

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

(
(setf child-of): Internal generic functions
(setf child-of): Internal generic functions
(setf degree-of): Internal generic functions
(setf degree-of): Internal generic functions
(setf head-of): Internal generic functions
(setf head-of): Internal generic functions
(setf key-of): Internal generic functions
(setf key-of): Internal generic functions
(setf parent-of): Internal generic functions
(setf parent-of): Internal generic functions
(setf sibling-of): Internal generic functions
(setf sibling-of): Internal generic functions
(setf test-of): Exported generic functions
(setf test-of): Exported generic functions

C
child-of: Internal generic functions
child-of: Internal generic functions

D
degree-of: Internal generic functions
degree-of: Internal generic functions

E
extract-extremum-key: Exported functions

F
Function, extract-extremum-key: Exported functions
Function, get-extremum-key: Exported functions
Function, get-prior-to-extremum: Internal functions
Function, insert-key: Exported functions
Function, link-siblings: Internal functions
Function, link-trees: Internal functions
Function, merge-siblings: Internal functions
Function, print-tree: Internal functions
Function, sexp->tree: Internal functions
Function, sibling-list: Internal functions
Function, tree->sexp: Internal functions
Function, unite-heaps: Exported functions
Function, unite-root-lists: Internal functions
Function, unsafe-unite-root-lists: Internal functions

G
Generic Function, (setf child-of): Internal generic functions
Generic Function, (setf degree-of): Internal generic functions
Generic Function, (setf head-of): Internal generic functions
Generic Function, (setf key-of): Internal generic functions
Generic Function, (setf parent-of): Internal generic functions
Generic Function, (setf sibling-of): Internal generic functions
Generic Function, (setf test-of): Exported generic functions
Generic Function, child-of: Internal generic functions
Generic Function, degree-of: Internal generic functions
Generic Function, head-of: Internal generic functions
Generic Function, key-of: Internal generic functions
Generic Function, parent-of: Internal generic functions
Generic Function, sibling-of: Internal generic functions
Generic Function, test-of: Exported generic functions
get-extremum-key: Exported functions
get-prior-to-extremum: Internal functions

H
head-of: Internal generic functions
head-of: Internal generic functions

I
insert-key: Exported functions

K
key-of: Internal generic functions
key-of: Internal generic functions

L
link-siblings: Internal functions
link-trees: Internal functions

M
Macro, prog1-let: Internal macros
Macro, when-let: Internal macros
merge-siblings: Internal functions
Method, (setf child-of): Internal generic functions
Method, (setf degree-of): Internal generic functions
Method, (setf head-of): Internal generic functions
Method, (setf key-of): Internal generic functions
Method, (setf parent-of): Internal generic functions
Method, (setf sibling-of): Internal generic functions
Method, (setf test-of): Exported generic functions
Method, child-of: Internal generic functions
Method, degree-of: Internal generic functions
Method, head-of: Internal generic functions
Method, key-of: Internal generic functions
Method, parent-of: Internal generic functions
Method, sibling-of: Internal generic functions
Method, test-of: Exported generic functions

P
parent-of: Internal generic functions
parent-of: Internal generic functions
print-tree: Internal functions
prog1-let: Internal macros

S
sexp->tree: Internal functions
sibling-list: Internal functions
sibling-of: Internal generic functions
sibling-of: Internal generic functions

T
test-of: Exported generic functions
test-of: Exported generic functions
tree->sexp: Internal functions

U
unite-heaps: Exported functions
unite-root-lists: Internal functions
unsafe-unite-root-lists: Internal functions

W
when-let: Internal macros

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

Next: , Previous: , Up: Indexes   [Contents][Index]

A.3 Variables

Jump to:   C   D   H   K   P   S   T  
Index Entry  Section

C
child: Internal classes

D
degree: Internal classes

H
head: Exported classes

K
key: Internal classes

P
parent: Internal classes

S
sibling: Internal classes
Slot, child: Internal classes
Slot, degree: Internal classes
Slot, head: Exported classes
Slot, key: Internal classes
Slot, parent: Internal classes
Slot, sibling: Internal classes
Slot, test: Exported classes

T
test: Exported classes

Jump to:   C   D   H   K   P   S   T  

Previous: , Up: Indexes   [Contents][Index]

A.4 Data types

Jump to:   B   C   P   S  
Index Entry  Section

B
binomial-heap: The binomial-heap system
binomial-heap: The binomial-heap package
binomial-heap: Exported classes
binomial-heap-system: The binomial-heap-system package
binomial-tree: Internal classes

C
Class, binomial-heap: Exported classes
Class, binomial-tree: Internal classes

P
Package, binomial-heap: The binomial-heap package
Package, binomial-heap-system: The binomial-heap-system package

S
System, binomial-heap: The binomial-heap system

Jump to:   B   C   P   S