Class LongHeap


  • public final class LongHeap
    extends java.lang.Object
    A min heap that stores longs; a primitive priority queue that like all priority queues maintains a partial ordering of its elements such that the least element can always be found in constant time. Put()'s and pop()'s require log(size). This heap provides unbounded growth via push(long), and bounded-size insertion based on its nominal maxSize via insertWithOverflow(long). The heap is a min heap, meaning that the top element is the lowest value of the heap.
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private long[] heap  
      private int maxSize  
      private int size  
    • Constructor Summary

      Constructors 
      Constructor Description
      LongHeap​(int maxSize)
      Create an empty priority queue of the configured initial size.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void clear()
      Removes all entries from the PriorityQueue.
      private void downHeap​(int i)  
      long get​(int i)
      Return the element at the ith location in the heap array.
      (package private) long[] getHeapArray()
      This method returns the internal heap array.
      boolean insertWithOverflow​(long value)
      Adds a value to an LongHeap in log(size) time.
      long pop()
      Removes and returns the least element of the PriorityQueue in log(size) time.
      long push​(long element)
      Adds a value in log(size) time.
      void pushAll​(LongHeap other)  
      int size()
      Returns the number of elements currently stored in the PriorityQueue.
      long top()
      Returns the least element of the LongHeap in constant time.
      long updateTop​(long value)
      Replace the top of the pq with newTop.
      private void upHeap​(int origPos)  
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • maxSize

        private final int maxSize
      • heap

        private long[] heap
      • size

        private int size
    • Constructor Detail

      • LongHeap

        public LongHeap​(int maxSize)
        Create an empty priority queue of the configured initial size.
        Parameters:
        maxSize - the maximum size of the heap, or if negative, the initial size of an unbounded heap
    • Method Detail

      • push

        public final long push​(long element)
        Adds a value in log(size) time. Grows unbounded as needed to accommodate new values.
        Returns:
        the new 'top' element in the queue.
      • insertWithOverflow

        public boolean insertWithOverflow​(long value)
        Adds a value to an LongHeap in log(size) time. If the number of values would exceed the heap's maxSize, the least value is discarded.
        Returns:
        whether the value was added (unless the heap is full, or the new value is less than the top value)
      • top

        public final long top()
        Returns the least element of the LongHeap in constant time. It is up to the caller to verify that the heap is not empty; no checking is done, and if no elements have been added, 0 is returned.
      • pop

        public final long pop()
        Removes and returns the least element of the PriorityQueue in log(size) time.
        Throws:
        java.lang.IllegalStateException - if the LongHeap is empty.
      • updateTop

        public final long updateTop​(long value)
        Replace the top of the pq with newTop. Should be called when the top value changes. Still log(n) worst case, but it's at least twice as fast to
         pq.updateTop(value);
         
        instead of
         pq.pop();
         pq.push(value);
         
        Calling this method on an empty LongHeap has no visible effect.
        Parameters:
        value - the new element that is less than the current top.
        Returns:
        the new 'top' element after shuffling the heap.
      • size

        public final int size()
        Returns the number of elements currently stored in the PriorityQueue.
      • clear

        public final void clear()
        Removes all entries from the PriorityQueue.
      • upHeap

        private void upHeap​(int origPos)
      • downHeap

        private void downHeap​(int i)
      • pushAll

        public void pushAll​(LongHeap other)
      • get

        public long get​(int i)
        Return the element at the ith location in the heap array. Use for iterating over elements when the order doesn't matter. Note that the valid arguments range from [1, size].
      • getHeapArray

        final long[] getHeapArray()
        This method returns the internal heap array.