minmaxheap.java

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

            swap(nodeIndex,grandparentIndex);
            nodeIndex = grandparentIndex;
        }
    }

    void bubbleUpMax(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;
            swap(nodeIndex,grandparentIndex);
            nodeIndex = grandparentIndex;
        }
    }


    boolean onMinLevel(int nodeIndex) {
        return mLevelTypes[nodeIndex];
    }

    void trickleDown(int nodeIndex) {
        if (noChildren(nodeIndex)) return;
        if (onMinLevel(nodeIndex))
            trickleDownMin(nodeIndex);
        else
            trickleDownMax(nodeIndex);
    }

    void trickleDownMin(int nodeIndex) {
        while (leftDaughterIndex(nodeIndex) < mNextFreeIndex) { // has dtrs
            int minDescIndex = minDtrOrGrandDtrIndex(nodeIndex);
            if (isDaughter(nodeIndex,minDescIndex)) {
                if (mHeap[minDescIndex].score() < mHeap[nodeIndex].score())
                    swap(minDescIndex,nodeIndex);
                return;
            } else {  // is grand child
                if (mHeap[minDescIndex].score() >= mHeap[nodeIndex].score())
                    return;
                swap(minDescIndex,nodeIndex);
                int parentIndex = parentIndex(minDescIndex);
                if (mHeap[minDescIndex].score() > mHeap[parentIndex].score())
                    swap(minDescIndex,parentIndex);
                nodeIndex = minDescIndex; // recursive call in paper
            }
        }
    }

    void trickleDownMax(int nodeIndex) {
        while (leftDaughterIndex(nodeIndex) < mNextFreeIndex) {
            int maxDescIndex = maxDtrOrGrandDtrIndex(nodeIndex);
            if (isDaughter(nodeIndex,maxDescIndex)) {
                if (mHeap[maxDescIndex].score() > mHeap[nodeIndex].score())
                    swap(maxDescIndex,nodeIndex);
                return;
            } else {  // is grand child
                if (mHeap[maxDescIndex].score() <= mHeap[nodeIndex].score())
                    return;
                swap(maxDescIndex,nodeIndex);
                int parentIndex = parentIndex(maxDescIndex);
                if (mHeap[maxDescIndex].score() < mHeap[parentIndex].score())
                    swap(maxDescIndex,parentIndex);
                nodeIndex = maxDescIndex; // recursive call in paper
            }
        }
    }


    // requires nodeIndex to have a dtr
    int minDtrOrGrandDtrIndex(int nodeIndex) {
        // start with left dtr; must have a dtr coming in
        int leftDtrIndex = leftDaughterIndex(nodeIndex);
        int minIndex = leftDtrIndex;
        double minScore = mHeap[leftDtrIndex].score();

        int rightDtrIndex = rightDaughterIndex(nodeIndex); 
        if (rightDtrIndex >= mNextFreeIndex) return minIndex;
        double rightDtrScore = mHeap[rightDtrIndex].score();
        if (rightDtrScore < minScore) {
            minIndex = rightDtrIndex;
            minScore = rightDtrScore;
        }
        
        int grandDtr1Index = leftDaughterIndex(leftDtrIndex);
        if (grandDtr1Index >= mNextFreeIndex) return minIndex;
        double grandDtr1Score = mHeap[grandDtr1Index].score();
        if (grandDtr1Score < minScore) {
            minIndex = grandDtr1Index;
            minScore = grandDtr1Score;
        }

        int grandDtr2Index = rightDaughterIndex(leftDtrIndex);
        if (grandDtr2Index >= mNextFreeIndex) return minIndex;
        double grandDtr2Score = mHeap[grandDtr2Index].score();
        if (grandDtr2Score < minScore) {
            minIndex = grandDtr2Index;
            minScore = grandDtr2Score;
        }

        int grandDtr3Index = leftDaughterIndex(rightDtrIndex);
        if (grandDtr3Index >= mNextFreeIndex) return minIndex;
        double grandDtr3Score = mHeap[grandDtr3Index].score();
        if (grandDtr3Score < minScore) {
            minIndex = grandDtr3Index;
            minScore = grandDtr3Score;
        }

        int grandDtr4Index = rightDaughterIndex(rightDtrIndex);
        if (grandDtr4Index >= mNextFreeIndex) return minIndex;
        double grandDtr4Score = mHeap[grandDtr4Index].score();

        return grandDtr4Score < minScore
            ? grandDtr4Index
            : minIndex;
    }


    // requires nodeIndex to have a dtr
    int maxDtrOrGrandDtrIndex(int nodeIndex) {
        // start with left dtr; must have a dtr coming in
        int leftDtrIndex = leftDaughterIndex(nodeIndex);
        int maxIndex = leftDtrIndex;
        double maxScore = mHeap[leftDtrIndex].score();

        int rightDtrIndex = rightDaughterIndex(nodeIndex); // opt to left+1
        if (rightDtrIndex >= mNextFreeIndex) return maxIndex;
        double rightDtrScore = mHeap[rightDtrIndex].score();
        if (rightDtrScore > maxScore) {
            maxIndex = rightDtrIndex;
            maxScore = rightDtrScore;
        }
        
        int grandDtr1Index = leftDaughterIndex(leftDtrIndex);
        if (grandDtr1Index >= mNextFreeIndex) return maxIndex;
        double grandDtr1Score = mHeap[grandDtr1Index].score();
        if (grandDtr1Score > maxScore) {
            maxIndex = grandDtr1Index;
            maxScore = grandDtr1Score;
        }

        int grandDtr2Index = rightDaughterIndex(leftDtrIndex);
        if (grandDtr2Index >= mNextFreeIndex) return maxIndex;
        double grandDtr2Score = mHeap[grandDtr2Index].score();
        if (grandDtr2Score > maxScore) {
            maxIndex = grandDtr2Index;
            maxScore = grandDtr2Score;
        }

        int grandDtr3Index = leftDaughterIndex(rightDtrIndex);
        if (grandDtr3Index >= mNextFreeIndex) return maxIndex;
        double grandDtr3Score = mHeap[grandDtr3Index].score();
        if (grandDtr3Score > maxScore) {
            maxIndex = grandDtr3Index;
            maxScore = grandDtr3Score;
        }

        int grandDtr4Index = rightDaughterIndex(rightDtrIndex);
        if (grandDtr4Index >= mNextFreeIndex) return maxIndex;
        double grandDtr4Score = mHeap[grandDtr4Index].score();

        return grandDtr4Score > maxScore
            ? grandDtr4Index
            : maxIndex;
    }

    boolean hasParent(int nodeIndex) {
        return nodeIndex > 1;
    }


    boolean noChildren(int nodeIndex) {
        return leftDaughterIndex(nodeIndex) >= mHeapLength;
    }
    
    boolean isDaughter(int nodeIndexParent, int nodeIndexDescendant) {
        return nodeIndexDescendant <= rightDaughterIndex(nodeIndexParent);
    }

    void swap(int index1, int index2) {
        Scored temp = mHeap[index1];
        mHeap[index1] = mHeap[index2];
        mHeap[index2] = temp;
    }
    

    static int parentIndex(int nodeIndex) {
        return nodeIndex/2;   // Java's int arith rounds down
    }

    static int leftDaughterIndex(int nodeIndex) {
        return 2 * nodeIndex;
    }

    static int rightDaughterIndex(int nodeIndex) {
        return 2 * nodeIndex + 1;
    }

    static void fillLevelTypes(boolean[] levelTypes) {
        boolean type = MAX_LEVEL;
        int index = 1;
        for (int numEltsOfType = 1; ; numEltsOfType *= 2) {  // 2**n per level
            type = !type;  // reverse types at each level
            for (int j = 0; j < numEltsOfType; ++j) {
                if (index >= levelTypes.length) return;
                levelTypes[index++] = type;
            }
        }
    }

    static final boolean MIN_LEVEL = true;
    static final boolean MAX_LEVEL = false;

    /*
    // not thread safe; defensive shallow copy; slow (n log n + object)
    // required for abs collex: iterator() + size()
    public Iterator iterator() {
        Scored[] result = new Scored[size()];
        for (int i = 1; i <= size(); ++i)
            result[i] = mHeap[i];
        Arrays.sort(result,Scored.SCORE_COMPARATOR);
        return new Arrays.asList(result).iterator();
    }


    // required for priority queue
    public Object peek() {
        return size() > 0 ? mHeap[1] : null;
    }

    public Object pop() {
        
    }
    */



}