The binomial-heap Reference Manual

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

The binomial-heap Reference Manual

This is the binomial-heap Reference Manual, generated automatically by Declt version 4.0 beta 2 "William Riker" on Tue Nov 15 04:18:03 2022 GMT+0.

Table of Contents


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.


2 Systems

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


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

2.1 binomial-heap

A compact binomial heap implementation.

Author

Volkan YAZICI <volkan.yazici@gmail.com>

License

BSD

Source

binomial-heap.asd.

Child Component

src (module).


3 Modules

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


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

3.1 binomial-heap/src

Source

binomial-heap.asd.

Parent Component

binomial-heap (system).

Child Components

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


4.1.1 binomial-heap/binomial-heap.asd

Source

binomial-heap.asd.

Parent Component

binomial-heap (system).

ASDF Systems

binomial-heap.

Packages

binomial-heap-system.


4.1.2 binomial-heap/src/packages.lisp

Source

binomial-heap.asd.

Parent Component

src (module).

Packages

binomial-heap.


4.1.3 binomial-heap/src/specials.lisp

Dependency

packages.lisp (file).

Source

binomial-heap.asd.

Parent Component

src (module).

Public Interface
Internals

4.1.4 binomial-heap/src/utils.lisp

Dependency

specials.lisp (file).

Source

binomial-heap.asd.

Parent Component

src (module).

Internals

4.1.5 binomial-heap/src/operations.lisp

Dependency

utils.lisp (file).

Source

binomial-heap.asd.

Parent Component

src (module).

Public Interface
Internals

5 Packages

Packages are listed by definition order.


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

5.1 binomial-heap

Source

packages.lisp.

Nickname

bh

Use List

common-lisp.

Public Interface
Internals

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

5.2 binomial-heap-system

Source

binomial-heap.asd.

Use List
  • asdf/interface.
  • common-lisp.

6 Definitions

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


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

6.1 Public Interface


6.1.1 Ordinary 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.

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.

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.

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.


6.1.2 Generic functions

Generic Reader: test-of (object)
Package

binomial-heap.

Methods
Reader Method: test-of ((binomial-heap binomial-heap))

automatically generated reader method

Source

specials.lisp.

Target Slot

test.

Generic Writer: (setf test-of) (object)
Package

binomial-heap.

Methods
Writer Method: (setf test-of) ((binomial-heap binomial-heap))

automatically generated writer method

Source

specials.lisp.

Target Slot

test.


6.1.3 Standalone methods

Method: print-object ((self binomial-tree) stream)
Source

specials.lisp.


6.1.4 Classes

Class: binomial-heap

Binomial heap container.

Package

binomial-heap.

Source

specials.lisp.

Direct methods
Direct slots
Slot: head
Type

list

Initargs

:head

Readers

head-of.

Writers

(setf head-of).

Slot: test
Type

function

Initargs

:test

Readers

test-of.

Writers

(setf test-of).


6.2 Internals


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

6.2.1 Macros

Macro: prog1-let ((var val) &body body)
Package

binomial-heap.

Source

utils.lisp.

Macro: when-let ((var val) &body body)
Package

binomial-heap.

Source

utils.lisp.


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

6.2.2 Ordinary 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.

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

Package

binomial-heap.

Source

operations.lisp.

Makes ‘X’ the child of ‘Y’.

Package

binomial-heap.

Source

operations.lisp.

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.

Function: print-tree (x)

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

Package

binomial-heap.

Source

operations.lisp.

Function: sexp->tree (sexp)

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

Package

binomial-heap.

Source

operations.lisp.

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.

Function: tree->sexp (tree)

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

Package

binomial-heap.

Source

operations.lisp.

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.

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.


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

6.2.3 Generic functions

Generic Reader: child-of (object)
Package

binomial-heap.

Methods
Reader Method: child-of ((binomial-tree binomial-tree))

automatically generated reader method

Source

specials.lisp.

Target Slot

child.

Generic Writer: (setf child-of) (object)
Package

binomial-heap.

Methods
Writer Method: (setf child-of) ((binomial-tree binomial-tree))

automatically generated writer method

Source

specials.lisp.

Target Slot

child.

Generic Reader: degree-of (object)
Package

binomial-heap.

Methods
Reader Method: degree-of ((binomial-tree binomial-tree))

automatically generated reader method

Source

specials.lisp.

Target Slot

degree.

Generic Writer: (setf degree-of) (object)
Package

binomial-heap.

Methods
Writer Method: (setf degree-of) ((binomial-tree binomial-tree))

automatically generated writer method

Source

specials.lisp.

Target Slot

degree.

Generic Reader: head-of (object)
Package

binomial-heap.

Methods
Reader Method: head-of ((binomial-heap binomial-heap))

automatically generated reader method

Source

specials.lisp.

Target Slot

head.

Generic Writer: (setf head-of) (object)
Package

binomial-heap.

Methods
Writer Method: (setf head-of) ((binomial-heap binomial-heap))

automatically generated writer method

Source

specials.lisp.

Target Slot

head.

Generic Reader: key-of (object)
Package

binomial-heap.

Methods
Reader Method: key-of ((binomial-tree binomial-tree))

automatically generated reader method

Source

specials.lisp.

Target Slot

key.

Generic Writer: (setf key-of) (object)
Package

binomial-heap.

Methods
Writer Method: (setf key-of) ((binomial-tree binomial-tree))

automatically generated writer method

Source

specials.lisp.

Target Slot

key.

Generic Reader: parent-of (object)
Package

binomial-heap.

Methods
Reader Method: parent-of ((binomial-tree binomial-tree))

automatically generated reader method

Source

specials.lisp.

Target Slot

parent.

Generic Writer: (setf parent-of) (object)
Package

binomial-heap.

Methods
Writer Method: (setf parent-of) ((binomial-tree binomial-tree))

automatically generated writer method

Source

specials.lisp.

Target Slot

parent.

Generic Reader: sibling-of (object)
Package

binomial-heap.

Methods
Reader Method: sibling-of ((binomial-tree binomial-tree))

automatically generated reader method

Source

specials.lisp.

Target Slot

sibling.

Generic Writer: (setf sibling-of) (object)
Package

binomial-heap.

Methods
Writer Method: (setf sibling-of) ((binomial-tree binomial-tree))

automatically generated writer method

Source

specials.lisp.

Target Slot

sibling.


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

6.2.4 Classes

Class: binomial-tree

Binomial tree container.

Package

binomial-heap.

Source

specials.lisp.

Direct methods
Direct slots
Slot: parent
Type

binomial-heap::binomial-tree

Initargs

:parent

Readers

parent-of.

Writers

(setf parent-of).

Slot: degree
Type

(integer 0 *)

Initform

0

Initargs

:degree

Readers

degree-of.

Writers

(setf degree-of).

Slot: child
Type

binomial-heap::binomial-tree

Initargs

:child

Readers

child-of.

Writers

(setf child-of).

Slot: sibling
Type

binomial-heap::binomial-tree

Initargs

:sibling

Readers

sibling-of.

Writers

(setf sibling-of).

Slot: key
Initargs

:key

Readers

key-of.

Writers

(setf key-of).


Appendix A Indexes


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

A.1 Concepts


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): Private generic functions
(setf child-of): Private generic functions
(setf degree-of): Private generic functions
(setf degree-of): Private generic functions
(setf head-of): Private generic functions
(setf head-of): Private generic functions
(setf key-of): Private generic functions
(setf key-of): Private generic functions
(setf parent-of): Private generic functions
(setf parent-of): Private generic functions
(setf sibling-of): Private generic functions
(setf sibling-of): Private generic functions
(setf test-of): Public generic functions
(setf test-of): Public generic functions

C
child-of: Private generic functions
child-of: Private generic functions

D
degree-of: Private generic functions
degree-of: Private generic functions

E
extract-extremum-key: Public ordinary functions

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

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

H
head-of: Private generic functions
head-of: Private generic functions

I
insert-key: Public ordinary functions

K
key-of: Private generic functions
key-of: Private generic functions

L
link-siblings: Private ordinary functions
link-trees: Private ordinary functions

M
Macro, prog1-let: Private macros
Macro, when-let: Private macros
merge-siblings: Private ordinary functions
Method, (setf child-of): Private generic functions
Method, (setf degree-of): Private generic functions
Method, (setf head-of): Private generic functions
Method, (setf key-of): Private generic functions
Method, (setf parent-of): Private generic functions
Method, (setf sibling-of): Private generic functions
Method, (setf test-of): Public generic functions
Method, child-of: Private generic functions
Method, degree-of: Private generic functions
Method, head-of: Private generic functions
Method, key-of: Private generic functions
Method, parent-of: Private generic functions
Method, print-object: Public standalone methods
Method, sibling-of: Private generic functions
Method, test-of: Public generic functions

P
parent-of: Private generic functions
parent-of: Private generic functions
print-object: Public standalone methods
print-tree: Private ordinary functions
prog1-let: Private macros

S
sexp->tree: Private ordinary functions
sibling-list: Private ordinary functions
sibling-of: Private generic functions
sibling-of: Private generic functions

T
test-of: Public generic functions
test-of: Public generic functions
tree->sexp: Private ordinary functions

U
unite-heaps: Public ordinary functions
unite-root-lists: Private ordinary functions
unsafe-unite-root-lists: Private ordinary functions

W
when-let: Private macros

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