heap.java

java 的源代码

package com.reddragon2046.base.utilities.data.algorithms;

import com.reddragon2046.base.utilities.data.*;

// Referenced classes of package com.reddragon2046.base.utilities.data.algorithms:
//            Predicates

public final class Heap
{

    private Heap()
    {
    }

    public static void pushHeap(BidirectionalIterator first, BidirectionalIterator last)
    {
        pushHeap(first, last, ((BinaryPredicate) (new Predicates.HashComparator())));
    }

    public static void pushHeap(BidirectionalIterator first, BidirectionalIterator last, BinaryPredicate comparator)
    {
        if(!first.isCompatibleWith(last))
        {
            throw new IllegalArgumentException("iterators not compatible");
        } else
        {
            pushHeap(first, first.distance(last) - 1, 0, last.get(-1), comparator);
            return;
        }
    }

    static void pushHeap(BidirectionalIterator first, int holeIndex, int topIndex, Object value, BinaryPredicate comparator)
    {
        int parent = (holeIndex - 1) / 2;
        BidirectionalIterator firstx;
        for(firstx = (BidirectionalIterator)first.clone(); holeIndex > topIndex && comparator.execute(firstx.get(parent), value); parent = (holeIndex - 1) / 2)
        {
            firstx.put(holeIndex, firstx.get(parent));
            holeIndex = parent;
        }

        firstx.put(holeIndex, value);
    }

    public static void popHeap(BidirectionalIterator first, BidirectionalIterator last)
    {
        popHeap(first, last, ((BinaryPredicate) (new Predicates.HashComparator())));
    }

    public static void popHeap(BidirectionalIterator first, BidirectionalIterator last, BinaryPredicate comparator)
    {
        if(!first.isCompatibleWith(last))
        {
            throw new IllegalArgumentException("iterators not compatible");
        } else
        {
            Object old = last.get(-1);
            last.put(-1, first.get());
            adjustHeap(first, 0, first.distance(last) - 1, old, comparator);
            return;
        }
    }

    public static void makeHeap(BidirectionalIterator first, BidirectionalIterator last)
    {
        makeHeap(first, last, ((BinaryPredicate) (new Predicates.HashComparator())));
    }

    public static void makeHeap(BidirectionalIterator first, BidirectionalIterator last, BinaryPredicate comparator)
    {
        if(!first.isCompatibleWith(last))
            throw new IllegalArgumentException("iterators not compatible");
        int len = first.distance(last);
        if(len < 2)
            return;
        int parent = (len - 2) / 2;
        do
        {
            adjustHeap(first, parent, len, first.get(parent), comparator);
            if(parent == 0)
                return;
            parent--;
        } while(true);
    }

    public static void sortHeap(BidirectionalIterator first, BidirectionalIterator last)
    {
        sortHeap(first, last, ((BinaryPredicate) (new Predicates.HashComparator())));
    }

    public static void sortHeap(BidirectionalIterator first, BidirectionalIterator last, BinaryPredicate comparator)
    {
        if(!first.isCompatibleWith(last))
            throw new IllegalArgumentException("iterators not compatible");
        for(BidirectionalIterator lastx = (BidirectionalIterator)last.clone(); first.distance(lastx) > 1; lastx.retreat())
            popHeap(first, lastx, comparator);

    }

    static void adjustHeap(BidirectionalIterator first, int holeIndex, int len, Object value, BinaryPredicate comparator)
    {
        int topIndex = holeIndex;
        int secondChild;
        for(secondChild = 2 * (holeIndex + 1); secondChild < len; secondChild = 2 * (secondChild + 1))
        {
            if(comparator.execute(first.get(secondChild), first.get(secondChild - 1)))
                secondChild--;
            first.put(holeIndex, first.get(secondChild));
            holeIndex = secondChild;
        }

        if(secondChild == len)
        {
            first.put(holeIndex, first.get(secondChild - 1));
            holeIndex = secondChild - 1;
        }
        pushHeap(first, holeIndex, topIndex, value, comparator);
    }
}