Class IntPriorityQueue


  • public final class IntPriorityQueue
    extends java.lang.Object
    A mix of a priority queue and a hashmap, specialized for ints
    Version:
    4.8
    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      (package private) static class  IntPriorityQueue.Node
      a node containing the data associated with each int
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      int addPriority​(int i, int amount)
      the priority of i is now the old priority (or 0) + the amount.
      private IntPriorityQueue.Node findLastNode()
      finds the rightmost node, at the last level of depth
      int getPriority​(int i)
      accesses the priority of i.
      int getTop()
      access the element with highest priority, or 0 if it is empty
      boolean isEmpty()
      checks if the priority queue is empty
      private void percolateDown()
      heapify the tree by swapping nodes (from the root) until the tree becomes a heap
      int percolateDown​(int i)
      equivalent to addPriority(i, -1);
      int percolateUp​(int i)
      equivalent to addPriority(i, 1)
      private void percolateUp​(IntPriorityQueue.Node n)
      balances the tree again so that the given node moves up (to be called when the current node has highest priority than its parent)
      void remove​(int i)
      forget about i.
      • Methods inherited from class java.lang.Object

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

      • IntPriorityQueue

        public IntPriorityQueue()
    • Method Detail

      • addPriority

        public int addPriority​(int i,
                               int amount)
        the priority of i is now the old priority (or 0) + the amount. The priority stays >= 0.
        Parameters:
        i - the int of which we want to modify the priority
        amount - the amount by which we modify the priority
        Returns:
        the new priority of i
      • percolateUp

        public int percolateUp​(int i)
        equivalent to addPriority(i, 1)
        Parameters:
        i - the int of which we want to modify the priority
        Returns:
        the new priority of i
      • percolateDown

        public int percolateDown​(int i)
        equivalent to addPriority(i, -1);
        Parameters:
        i - the int of which we want to modify the priority
        Returns:
        the new priority of i
      • getPriority

        public int getPriority​(int i)
        accesses the priority of i. If i had no priority, returns 0.
        Parameters:
        i - the int
        Returns:
        the priority of i
      • remove

        public void remove​(int i)
        forget about i. Next call to getPriority(i) will be 0.
        Parameters:
        i - the int to forget
      • getTop

        public int getTop()
        access the element with highest priority, or 0 if it is empty
        Returns:
        the element with highest priority, or 0 if it is empty
      • isEmpty

        public boolean isEmpty()
        checks if the priority queue is empty
        Returns:
        true if the priority queue is empty and false otherwise
      • findLastNode

        private IntPriorityQueue.Node findLastNode()
        finds the rightmost node, at the last level of depth
        Returns:
        this node, or null
      • percolateDown

        private final void percolateDown()
        heapify the tree by swapping nodes (from the root) until the tree becomes a heap
      • percolateUp

        private final void percolateUp​(IntPriorityQueue.Node n)
        balances the tree again so that the given node moves up (to be called when the current node has highest priority than its parent)
        Parameters:
        n - the node