___ __ __ ____ _ __ ___ __ _ _ ____ ___ ____
 .\ _\ \\ \/\ _\ \   ___ _\ __\ \  . \
 .<_ / \ .  \ / . \ _____\ _  ]_ . \ __/
___// /\_/___//v\// /\_/___/ / /___//\_//
 '( A B S T R A C T ) 
Binomialheap is a compact and succint implementation of binomial heap data
structure[1] in Common Lisp programming language. Data structure performs
insertion, extremum access, extremum extraction, and union operations in O(logn)
time.
[1] http://en.wikipedia.org/wiki/Binomial_heap
 '( D E M O ) 
(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 #'<))
; => #
(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
 '( C A V E A T S ) 
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:
Swapping Key Fields
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.
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 (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.)
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 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.
 '( L I C E N S E ) 
Copyright (c) 2009, Volkan YAZICI
All rights reserved.
Redistribution and use in source and binary forms, with or without modification,
are permitted provided that the following conditions are met:
 Redistributions of source code must retain the above copyright notice, this
list of conditions and the following disclaimer.
 Redistributions in binary form must reproduce the above copyright notice, this
list of conditions and the following disclaimer in the documentation and/or
other materials provided with the distribution.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.