Voici une implémentation des tas binomiaux, j'ai commencé par écrire quelques fonctions de gestion de listes chaînées, et j'ai crée deux classes pour représenter respectivement les arbres binomiaux et les tas binomiaux.
/**
Implements a very simple linked list, each link points to item
of type T and references the next link. O(1) operations are
getting the first link's data or the second's link reference,
or deleting the first element. Each functions modifying the
linking returns a pointer to the first link of the list.
*/
public class LinkedList<T>
{
/************************************************/
private T data;
/************************************************/
private LinkedList<T> next;
/************************************************/
/**
Creates a one element list.
*/
public LinkedList(T data)
{
this.data = data;
}
/************************************************/
/**
Creates a one link list and appends the second
paramter to this list.
*/
public LinkedList(T data, LinkedList<T> next)
{
this(data);
this.next = next;
}
/************************************************/
/**
Modifies the data.
*/
public void setData(T data)
{
this.data = data;
}
/************************************************/
/**
Appends a list to the first link of the current
list.
*/
public void setNext(LinkedList<T> next)
{
this.next = next;
}
/************************************************/
/**
Retrives the data of the first link.
*/
public T getData()
{
return data;
}
/************************************************/
/**
Returns the second item of the list, doesn't change
the linking
*/
public LinkedList<T> getNext()
{
return next;
}
/************************************************/
/**
Delete from this list the link which the adress is l,
returns the list whithout l.
*/
public LinkedList<T> deleteLink(LinkedList<T> l)
{
if (this == l)
return getNext();
setNext(getNext().deleteLink(l));
return this;
}
/************************************************/
/**
Returns a String representation of the list.
*/
public String toString()
{
return " -> " + data +
((next != null) ? next.toString() : "X");
}
/************************************************/
private static <K> LinkedList<K> reverseAcc(LinkedList<K> link,
LinkedList<K> acc)
{
if (link == null)
return acc;
LinkedList<K> next = link.getNext();
link.setNext(acc);
return reverseAcc(next, link);
}
/************************************************/
/**
Adds the link l in front of this list, returns
the list thus created.
*/
public LinkedList<T> addFront(LinkedList<T> l)
{
l.setNext(this);
return l;
}
/************************************************/
/**
Adds the item o in front of this list, returns
the new list.
*/
public LinkedList<T> addFront(T o)
{
return addFront(new LinkedList<T>(o));
}
/************************************************/
/**
Reverse the order of the items of the list. Returns the
new list.
*/
public LinkedList<T> reverse()
{
return reverseAcc(this, null);
}
}
class BinomialTree<T extends Comparable<T>>
implements Comparable<BinomialTree<T>>
{
/************************************************/
private int order;
/************************************************/
private T data;
/************************************************/
private LinkedList<BinomialTree<T>> sons;
/************************************************/
public BinomialTree(T data)
{
this.data = data;
order = 0;
sons = null;
}
/************************************************/
public BinomialTree<T> fusion(BinomialTree<T> other)
{
if (getData().compareTo(other.getData()) > 0)
return other.fusion(this);
if (order != other.getOrder())
System.out.println("Invalid arguments");
sons = (sons == null) ?
new LinkedList<BinomialTree<T>>(other) :
sons.addFront(other);
order++;
return this;
}
/************************************************/
public int getOrder()
{
return order;
}
/************************************************/
public T getData()
{
return data;
}
/************************************************/
public BinomialHeap<T> extractSons()
{
return new BinomialHeap<T>((sons == null) ?
null :
sons.reverse()
);
}
/************************************************/
public int compareTo(BinomialTree<T> other)
{
if (order < other.getOrder())
return -1;
if (order == other.getOrder())
return 0;
return 1;
}
}
/**
Implements a priority queue which allows the following operations,
each one in a in O(log n) time.
- inserting an item
- getting the minimum key item
- deleting the minimum key item
- merging two queues
It has been implemented by alexandre-mesle.com for java 1.5
*/
public class BinomialHeap<T extends Comparable<T>>
{
/************************************************/
private LinkedList<BinomialTree<T>> binomialTrees;
/************************************************/
/**
Creates an empty queue.
*/
public BinomialHeap()
{
binomialTrees = null;
}
/************************************************/
/**
Creates a one item queue.
*/
public BinomialHeap(T data)
{
binomialTrees = new LinkedList<BinomialTree<T>>
(new BinomialTree<T>(data));
}
/************************************************/
BinomialHeap(LinkedList<BinomialTree<T>> l)
{
binomialTrees = l;
}
/************************************************/
/**
Returns trus if and only if the queue doesn't contain
any item.
*/
public boolean isEmpty()
{
return binomialTrees == null;
}
/************************************************/
private static <K extends Comparable<K>> LinkedList<BinomialTree<K>>
findMinLink(LinkedList<BinomialTree<K>> link,
LinkedList<BinomialTree<K>> acc)
{
if (link == null)
return acc;
K linkData = link.getData().getData();
K accData = acc.getData().getData();
if (linkData.compareTo(accData) < 1)
return findMinLink(link.getNext(), link);
return findMinLink(link.getNext(), acc);
}
/************************************************/
/**
Returns the item wich has the minimum key.
*/
public T getMin()
{
LinkedList<BinomialTree<T>> minNode = findMinLink(binomialTrees,
binomialTrees);
if (minNode == null)
return null;
return minNode.getData().getData();
}
/************************************************/
/**
Deletes the minimum key item.
*/
public void deleteMin()
{
LinkedList<BinomialTree<T>> minLink =
findMinLink(binomialTrees, binomialTrees);
binomialTrees = binomialTrees.deleteLink(minLink);
BinomialHeap<T> sons = minLink.getData().extractSons();
fusion(sons);
}
/************************************************/
/**
Deletes the minimum key item.
*/
public void insert(T c)
{
fusion(new BinomialHeap<T>(c));
}
/************************************************/
/**
Adds to the current queue all the item of the queue b.
Use it only if b doesn't have to used again.
*/
public void fusion(BinomialHeap<T> b)
{
binomialTrees =
clean(merge(binomialTrees, b.binomialTrees));
}
/************************************************/
private static <K extends Comparable<K>> LinkedList<BinomialTree<K>>
merge(LinkedList<BinomialTree<K>> l1,
LinkedList<BinomialTree<K>> l2)
{
if (l1 == null)
return l2;
if (l2 == null)
return l1;
if (l1.getData().compareTo(l2.getData()) <= 0)
{
l1.setNext(merge(l1.getNext(), l2));
return l1;
}
else
return merge(l2, l1);
}
/************************************************/
private static <K extends Comparable<K>> LinkedList<BinomialTree<K>>
clean(LinkedList<BinomialTree<K>> l)
{
if (l == null)
return null;
if (l.getNext() == null)
return l;
BinomialTree<K> first = l.getData();
BinomialTree<K> second = l.getNext().getData();
if (first.getOrder() != second.getOrder())
{
l.setNext(clean(l.getNext()));
return l;
}
if (l.getNext().getNext() == null)
return new LinkedList<BinomialTree<K>>
(first.fusion(second),
l.getNext().getNext());
BinomialTree<K> third = l.getNext().getNext().getData();
if (first.getOrder() == third.getOrder())
{
l.setNext(clean(l.getNext()));
return l;
}
else
return new LinkedList<BinomialTree<K>>
(first.fusion(second),
l.getNext().getNext());
}
/************************************************/
/*
public static void main(String[] args)
{
BinomialHeap<Integer> h = new BinomialHeap<Integer>();
for (int i = 1 ; i < 3000 ; i++)
h.insert(new Integer((i*i*i*i*i*i*i) % 127));
while(!h.isEmpty())
{
System.out.print(h.getMin() + " -> ");
h.deleteMin();
}
}
*/
}