binomialheap.java

一个关于java 的常用工具包

package org.jutil.java.collections;

import java.util.Comparator;

/**
 * <p>A BinomialHeap is a Heap with most of
 *    its operations <b>O(1)</b> or <b>O(log(1))</b>.<p>
 * 
 * @author Tom Schrijvers
 * @release $Name:  $
 */
public class BinomialHeap extends AbstractPriorityQueue {

	private final BasicBinomialHeap rest;
	private Object root = null;
	
	/**
	 * Initialize a new BinomialHeap with the given comparator.
	 *
	 * @param comparator
	 *        The comparator that is used to determine the order
	 *        of the elements.
	 */
 /*@
   @ public behavior
   @
	 @ pre comparator != null;
	 @
	 @ post getComparator() == comparator;
	 @ post size() == 0;
	 @*/
	public BinomialHeap(Comparator comparator) {
		rest = new BasicBinomialHeap(comparator);
	}

	/**
	 * Initialize a new BinomialHeap with the given comparator
	 * and element.
	 *
	 * @param comparator
	 *        The comparator that is used to determine the order
	 *        of the elements.
	 * @param root
	 *        The initial element in the new BinomialHeap.
	 */
 /*@
   @ public behavior
	 @
	 @ pre comparator != null;
	 @ pre root != null;
	 @
	 @ post getComparator() == comparator;
	 @ post nbExplicitOccurrences(root) == 1;
	 @ post size() == 1;
	 @*/
	public BinomialHeap(Comparator comparator, Object root) {
		this(comparator);
		this.root = root;
	}

	/**
	 * <p>See superclass.</p>
	 */
	public Comparator getComparator() {
		return rest.getComparator();
	}
	
	/**
	 * <p>See superclass.</p>
	 *
	 * <p><b>O(log(n))</b></p>
	 */
	protected void addImpl(Object value) {
		if ( root == null ) {
			root = value;
			return;
		}
		if ( getComparator().compare(root, value) < 0) {
			rest.add(value);
		} else {
			rest.add(root);
			root = value;
		}
	}

	/**
	 * <p>See superclass.</p>
	 *
	 * <p><b>O(1)</b></p>
	 */
	public Object min() {
		return root;
	}

	/**
	 * <p>See superclass.</p>
	 * 
	 * <p><b>O(log(n))</b></p>
	 */
	public Object pop() {
		Object result = root;
		if ( ! rest.isEmpty() ) {
			root = rest.pop();
		} else {
			root = null;
		}
		return result;
	}

	/**
	 * <p>Add all elements in the given BinomialHeap to this heap
	 * and empty that heap.</p>
	 * 
	 * @param heap
	 *        The heap of which the elements are to be added to this heap.
	 *        
	 * <p><b>O(log((n))</b></p>
	 */
 /*@
   @ public behavior
	 @
	 @ pre heap != null;
	 @ pre (\forall Object a,b; heap.nbExplicitOccurrences(a) > 0 &&
	 @                          heap.nbExplicitOccurrences(b) > 0 
	 @                        ; getComparator().compare(a, b) == 0    ||
	 @                          heap.getComparator().compare(a, b) == 0 ||
	 @                          getComparator().compare(a, b) * heap.getComparator().compare(a, b) > 0 );
	 @                           
	 @ 
	 @ post size() == \old(size()) + \old(heap.size());
	 @ post (\forall Object element; ;
	 @               nbExplicitOccurrences(element) == \old(nbExplicitOccurrences(element)) + 
	 @                                                 \old(heap.nbExplicitOccurrences(element)));
	 @ post (\forall Object element; ;
	 @               heap.nbExplicitOccurrences(element) == 0);
	 @*/
	public void merge(BinomialHeap heap) {
		rest.merge(heap.rest);
		if ( getComparator().compare(root, heap.root) > 0) {
			rest.add(root);
			root = heap.root;
		} else {
			rest.add(heap.root);
		}
	}

	
	/**
	 * <p>See superclass</p>
	 */
	public void clear() {
		root = null;
		rest.clear();
	}

	/**
	 * <p>See superclass.</p>
	 *
	 * <p><b>O(n)</b></p>
	 */
	public int nbExplicitOccurrences(Object element) {
		if ( element == null ) {
			return 0;
		}
		return rest.nbExplicitOccurrences(element) + (root == element ? 1 : 0);
	}

	/**
	 * <p>See superclass.</p>
	 */
	public int size() {
		return (root == null ? 0 : 1 ) + rest.size();
	}

}
/*
 * <copyright>Copyright (C) 1997-2001. This software is copyrighted by 
 * the people and entities mentioned after the "@author" tags above, on 
 * behalf of the JUTIL.ORG Project. The copyright is dated by the dates 
 * after the "@date" tags above. All rights reserved.
 * This software is published under the terms of the JUTIL.ORG Software
 * License version 1.1 or later, a copy of which has been included with
 * this distribution in the LICENSE file, which can also be found at
 * http://org-jutil.sourceforge.net/LICENSE. This software is distributed 
 * WITHOUT ANY WARRANTY; without even the implied warranty of 
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 
 * See the JUTIL.ORG Software License for more details. For more information,
 * please see http://org-jutil.sourceforge.net/</copyright>
 */