minmaxheap.java

一个自然语言处理的Java开源工具包。LingPipe目前已有很丰富的功能

package com.aliasi.util;

import java.util.AbstractCollection;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;

/**
 * A <code>MinMaxHeap</code> provides a heap-like data structure that
 * provides fast access to both the minimum and maximum elements of
 * the heap.  Each min-max heap is of a fixed maximum size.  A min-max
 * heap holds elements implementing the {@link Scored} interface, with
 * scores being used for sorting.
 *
 * <p>A min-max heap data structure is useful to implement priority
 * queues with fixed numbers of elements, which requires access to
 * both the best and worst elements of the queue.
 * 
 * <p>This implementation is based on the paper:
 * <ul>
 * <li>Atkinson, M.D., J.-R. Sack, N. Santoro and T. Strothotte.  
 *     1986.
 *     <a href="http://www.cs.otago.ac.nz/staffpriv/mike/Papers/MinMaxHeaps/MinMaxHeaps.pdf">Min-max heaps and generalized priority queues</a>.
 *     <i>Communicatiosn of the ACM</i> <b>29</b>(10):996-1000.
 * </li>
 * </ul>      
 *
 * @author  Bob Carpenter
 * @version 3.0
 * @since   LingPipe2.4.0
 */
public class MinMaxHeap<E extends Scored> extends AbstractCollection<E> {

    // index starts at 1 to follow article
    // min at root and at even levels; max at root dtrs
    private final Scored[] mHeap;  

    private final int mHeapLength;

    // true for min levels
    private final boolean[] mLevelTypes;

    private int mNextFreeIndex = 1;

    /**
     * Construct a min-max heap holding up to the specified
     * number of elements.   Min-max heaps do not grow
     * dynamically and attempts to push an element onto a full
     * heap will result in exceptions.
     *
     * @param maxSize Maximum number of elements in the heap.
     */
    public MinMaxHeap(int maxSize) {
        if (maxSize < 1) {
            String msg = "Heaps must be at least one element."
                + " Found maxSize=" + maxSize;
            throw new IllegalArgumentException(msg);
        }
        mHeap = new Scored[maxSize+1];
        mHeapLength = mHeap.length;
        mLevelTypes = new boolean[maxSize+1];
        fillLevelTypes(mLevelTypes);
    }

    /**
     * Returns the current size of this heap.
     *
     * @return The size of the heap.
     */
    public int size() {
        return mNextFreeIndex - 1;
    }


    /**
     * Returns an iterator over this heap.  The elements are returned
     * in decreasing order of score.
     *
     * @return Iterator over this heap in decreasing order of score.
     */
    public Iterator<E> iterator() {
	ArrayList<E> list = new ArrayList<E>();
	for (int i = 0; i < mNextFreeIndex; ++i)
	    list.add((E) mHeap[i]);
	Collections.<E>sort(list,Scored.REVERSE_SCORE_COMPARATOR);
	return list.iterator();
    }

    /**
     * Add the element to the heap.
     * 
     * @param s Element to add to heap.
     * @return <code>true</code> if the element is added.
     */
    public boolean add(E s) {
        // space still left
        if (mNextFreeIndex < mHeapLength) {
            mHeap[mNextFreeIndex++] = s;
            bubbleUp(mNextFreeIndex-1);
            return true;
        } else if (s.score() <= peekMin().score()) {
            return false;
        } else {
            popMin();
            mHeap[mNextFreeIndex++] = s;
            bubbleUp(mNextFreeIndex-1);
            return true;
        }
    }

    /** 
     * Returns the maximum element in the heap, or <code>null</code>
     * if it is empty.
     *
     * @return The largest element in the heap.
     */
    public E peekMax() {
        return (E)
	    ( mNextFreeIndex == 1
	      ? null
	      : (mNextFreeIndex == 2
		 ? mHeap[1]
		 : (mNextFreeIndex == 3
		    ? mHeap[2]
		    : ( mHeap[2].score() > mHeap[3].score()
			? mHeap[2]
			: mHeap[3] ) ) ) );
    }


    /** 
     * Returns the minimum element in the heap, or <code>null</code>
     * if it is empty.
     *
     * @return The smallest element in the heap.
     */
    public E peekMin() {
        return (E) 
	    ( mNextFreeIndex == 1
	      ? null
	      : mHeap[1] );
    }

    /** 
     * Returns the maximum element in the heap after removing it, or
     * returns <code>null</code> if the heap is empty.
     *
     * @return The largest element in the heap.
     */
    public E popMax() {
        if (mNextFreeIndex == 1) return null;
        
        // only one element; return it
        if (mNextFreeIndex == 2) {
            --mNextFreeIndex;
            return (E) mHeap[1];
        }
        
        // two elements, so max is only on second level
        if (mNextFreeIndex == 3) {
            --mNextFreeIndex;
            return (E) mHeap[2];
        }
        
        // at least three elements, so check level 1 dtrs
        if (mHeap[2].score() > mHeap[3].score()) {
            Scored max = mHeap[2];
            mHeap[2] = mHeap[--mNextFreeIndex];
            trickleDownMax(2);
            return (E) max;
        } else {
            Scored max = mHeap[3];
            mHeap[3] = mHeap[--mNextFreeIndex];
            trickleDownMax(3);
            return (E) max;
        }
    }

    /** 
     * Returns the minimum element in the heap after removing it, or
     * returns <code>null</code> if the heap is empty.
     *
     * @return The smallest element in the heap.
     */
    public E popMin() { 
        if (mNextFreeIndex == 1) return null;

        if (mNextFreeIndex == 2) {
            mNextFreeIndex = 1;
            return (E) mHeap[1];
        }

        Scored min = mHeap[1];
        mHeap[1] = mHeap[--mNextFreeIndex];
        trickleDownMin(1);
        return (E) min;
    }

    /**
     * Returns a string-based representation of this heap.
     *
     * @return String representation of this heap.
     */
    public String toString() {
        if (mNextFreeIndex == 1) return "EMPTY HEAP";
        StringBuffer sb = new StringBuffer();
        for (int i = 1; i < mNextFreeIndex; ++i) {
            if (i > 1) sb.append("\n");
            sb.append(i + "=" + mHeap[i]);
        }
        return sb.toString();
    }

    void bubbleUp(int nodeIndex) {
        if (!hasParent(nodeIndex)) return;
        int parentIndex = parentIndex(nodeIndex);
        if (onMinLevel(nodeIndex)) {
            if (mHeap[nodeIndex].score() > mHeap[parentIndex].score()) {
                swap(nodeIndex,parentIndex);
                bubbleUpMax(parentIndex);
            } else {
                bubbleUpMin(nodeIndex);
            }
        } else {  // on max level
            if (mHeap[nodeIndex].score() < mHeap[parentIndex].score()) {
                swap(nodeIndex,parentIndex);
                bubbleUpMin(parentIndex);
            } else {
                bubbleUpMax(nodeIndex);
            }
        }
    }

    void bubbleUpMin(int nodeIndex) {
        while (true) {
            if (!hasParent(nodeIndex)) return;
            int parentIndex = parentIndex(nodeIndex);
            if (!hasParent(parentIndex)) return;
            int grandparentIndex = parentIndex(parentIndex);
            if (mHeap[nodeIndex].score() 
                >= mHeap[grandparentIndex].score()) return;