Class ObjectIndirectHeaps


  • public final class ObjectIndirectHeaps
    extends Object
    A class providing static methods and objects that do useful things with indirect heaps.

    An indirect heap is an extension of a semi-indirect heap using also an inversion array of the same length as the reference array, satisfying the relation heap[inv[i]]==i when inv[i]>=0, and inv[heap[i]]==i for all elements in the heap.

    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      static <K> int downHeap​(K[] refArray, int[] heap, int[] inv, int size, int i, Comparator<K> c)
      Moves the given element down into the indirect heap until it reaches the lowest possible position.
      static <K> void makeHeap​(K[] refArray, int[] heap, int[] inv, int size, Comparator<K> c)
      Creates an indirect heap from a given index array.
      static <K> void makeHeap​(K[] refArray, int offset, int length, int[] heap, int[] inv, Comparator<K> c)
      Creates an indirect heap in the given array.
      static <K> int upHeap​(K[] refArray, int[] heap, int[] inv, int size, int i, Comparator<K> c)
      Moves the given element up in the indirect heap until it reaches the highest possible position.
    • Method Detail

      • downHeap

        public static <K> int downHeap​(K[] refArray,
                                       int[] heap,
                                       int[] inv,
                                       int size,
                                       int i,
                                       Comparator<K> c)
        Moves the given element down into the indirect heap until it reaches the lowest possible position.
        Parameters:
        refArray - the reference array.
        heap - the indirect heap (starting at 0).
        inv - the inversion array.
        size - the number of elements in the heap.
        i - the index in the heap of the element to be moved down.
        c - a type-specific comparator, or null for the natural order.
        Returns:
        the new position in the heap of the element of heap index i.
      • upHeap

        public static <K> int upHeap​(K[] refArray,
                                     int[] heap,
                                     int[] inv,
                                     int size,
                                     int i,
                                     Comparator<K> c)
        Moves the given element up in the indirect heap until it reaches the highest possible position. Note that in principle after this call the heap property may be violated.
        Parameters:
        refArray - the reference array.
        heap - the indirect heap (starting at 0).
        inv - the inversion array.
        size - the number of elements in the heap.
        i - the index in the heap of the element to be moved up.
        c - a type-specific comparator, or null for the natural order.
        Returns:
        the new position in the heap of the element of heap index i.
      • makeHeap

        public static <K> void makeHeap​(K[] refArray,
                                        int offset,
                                        int length,
                                        int[] heap,
                                        int[] inv,
                                        Comparator<K> c)
        Creates an indirect heap in the given array.
        Parameters:
        refArray - the reference array.
        offset - the first element of the reference array to be put in the heap.
        length - the number of elements to be put in the heap.
        heap - the array where the heap is to be created.
        inv - the inversion array.
        c - a type-specific comparator, or null for the natural order.
      • makeHeap

        public static <K> void makeHeap​(K[] refArray,
                                        int[] heap,
                                        int[] inv,
                                        int size,
                                        Comparator<K> c)
        Creates an indirect heap from a given index array.
        Parameters:
        refArray - the reference array.
        heap - an array containing indices into refArray.
        inv - the inversion array.
        size - the number of elements in the heap.
        c - a type-specific comparator, or null for the natural order.