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


--- '( A B S T R A C T ) -------------------------------------------------------

Binomial-heap is a compact and  succint implementation of the binomial heap data
structure[1] in  Common Lisp  programming language. Insertion,  extremum access,
extremum extraction, and union operations can be performed on the data structure
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* (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


--- '( 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 `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.


--- '( L I C E N S E ) ---------------------------------------------------------

Copyright (c) 2009, Volkan YAZICI <volkan.yazici@gmail.com>
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.