User:Jdev/Code/Heap sort

In Tomcat i has been faced with follow problem: i have an unordered array of hundreds elements and i need get only 5-10 elements (but i do not know exactly how many). My first approach was to sort all array and get first five, but in this case most part of time was spend for nothing. To solve this problem i use now heap sort, which gives every step one greatest element and do not spent time to sort elements which never used. Following code use Tomcat's specific classes, but it's demonstrate the idea and can be easy adopted for any robot.

public class HeapSort {

    private final RTreeEntry[] array;
    private int i;

    public HeapSort(RTreeEntry[] array) {
        this.array = array;
        for (int i = array.length / 2; i >= 0; i--) {
            downHeap(i, array.length);
        }
        i = array.length - 1;
    }

    public void sortLastN(int n) {
        for (; i > 1 && i >= array.length - n; i--) {
            final RTreeEntry temp = array[i];
            array[i] = array[0];
            array[0] = temp;

            downHeap(0, i);
        }
    }

    private void downHeap(int k, int n) {
        RTreeEntry newElem = array[k];
        int child;

        while (k < n / 2) {
            child = (2 * k) + 1;
            if (child < n - 1 && array[child].location.roundTime < array[child + 1].location.roundTime) {
                child++;
            }
            if (newElem.location.roundTime > array[child].location.roundTime) {
                break;
            }
            array[k] = array[child];
            k = child;
        }
        array[k] = newElem;
    }

}

Usage of this class:

    int sortedEntris = BULLETS_PER_LOG;
    final HeapSort heapSort= new HeapSort(entries);
    heapSort.sortLastN(BULLETS_PER_LOG);    
    // other stuff
    for (int i = entries.length - 1; i >= 0; i--) {
        if (notShadowedBulletsCount == BULLETS_PER_LOG) {
            break;
        }
        if (i < entries.length - sortedEntris) {
            int entriesToSort = BULLETS_PER_LOG - notShadowedBulletsCount;
            sortedEntris += entriesToSort;
            heapSort.sortLastN(sortedEntris);
        }
        final LoadedRTreeEntry<UndirectedGuessFactor> entry = (LoadedRTreeEntry<UndirectedGuessFactor>) entries[i];
        // other stuff
    }