Module org.cicirello.core
Package org.cicirello.ds

Class IntBinaryHeap

java.lang.Object
org.cicirello.ds.IntBinaryHeap
All Implemented Interfaces:
IntPriorityQueue, Copyable<IntBinaryHeap>
public class IntBinaryHeap extends Object implements IntPriorityQueue, Copyable<IntBinaryHeap>
An implementation of a Binary Heap of (element, priority) pairs, such that the elements are distinct integers in the interval [0, n), and with priority values also of type int.

Priority order: IntBinaryHeap instances are created via factory methods with names beginning with create. The priority order depends upon the factory method used to create the IntBinaryHeap. Methods named createMinHeap produce a min heap with priority order minimum-priority-first-out. Methods named createMaxHeap produce a max heap with priority order maximum-priority-first-out.

Creating instances: To create an instance, use one of the factory methods. In this example an IntBinaryHeap with an element domain of [0,100) is created: 


 IntBinaryHeap<String> pq = IntBinaryHeap.createMinHeap(100);

In the above example, the element domain is [0,100) and the IntBinaryHeap is initially empty.

Purpose: The purpose of such an IntBinaryHeap is to support implementations of algorithms that require such a specialized case. For example, some graph algorithms such as Dijkstra's algorithm for single-source shortest paths, and Prim's algorithm for minimum spanning tree, rely on a priority queue of the vertex ids, which are usually ints in some finite range. Although such applications could use the classes that instead implement the PriorityQueue interface, using Java's wrapper type Integer, the classes that implement IntPriorityQueue that specialize the element type to int are optimized for this special case.

For a more general purpose binary heap, see the BinaryHeap class.

Method runtimes: The asymptotic runtime of the methods of this class are as follows (where n is the current size of the heap):

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    change(int element, int priority)
    Changes the priority of an element if the element is present in the IntPriorityQueue, and otherwise adds the (element, priority) pair to the IntPriorityQueue.
    final void
    clear()
    Clears the IntPriorityQueue, removing all elements.
    final boolean
    contains(int element)
    Checks if an element is in the IntPriorityQueue.
    IntBinaryHeap
    copy()
    Creates an identical copy of this object.
    static IntBinaryHeap
    createMaxHeap(int n)
    Initializes an empty max-heap of (int, priority) pairs, such that the domain of the elements are the integers in [0, n).
    static IntBinaryHeap
    createMinHeap(int n)
    Initializes an empty min-heap of (int, priority) pairs, such that the domain of the elements are the integers in [0, n).
    boolean
    demote(int element, int priority)
    Demotes an element relative to priority order if the element is present in the IntPriorityQueue.
    final int
    domain()
    Returns the domain of this IntPriorityQueue.
    final boolean
    isEmpty()
    Checks if the IntPriorityQueue is empty.
    boolean
    offer(int element, int priority)
    Adds an (element, priority) pair to the IntPriorityQueue with a specified priority, provided the element is not already in the IntPriorityQueue.
    final int
    peek()
    Gets the next element in priority order from this IntPriorityQueue, without removing it.
    int
    peekPriority()
    Gets the priority of the next element in priority order in the IntPriorityQueue.
    int
    peekPriority(int element)
    Gets the current priority of a specified element in the IntPriorityQueue.
    final int
    poll()
    Gets and removes the next element in priority order from this IntPriorityQueue.
    boolean
    promote(int element, int priority)
    Promotes an element relative to priority order if the element is present in the IntPriorityQueue.
    final int
    size()
    Gets the current size of the IntPriorityQueue, which is the number of (element, priority) pairs that it contains.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Method Details

    • copy

      public IntBinaryHeap copy()
      Description copied from interface: Copyable
      Creates an identical copy of this object.
      Specified by:
      copy in interface Copyable<IntBinaryHeap>
      Returns:
      an identical copy of this object.

    • change

      public boolean change(int element, int priority)
      Changes the priority of an element if the element is present in the IntPriorityQueue, and otherwise adds the (element, priority) pair to the IntPriorityQueue.
      Specified by:
      change in interface IntPriorityQueue
      Parameters:
      element - The element whose priority is to change.
      priority - Its new priority.
      Returns:
      true if and only if the IntPriorityQueue changed as a consequence of this method call.
      Throws:
      IndexOutOfBoundsException - if element is negative, or if element is greater than or equal to the domain n.

    • clear

      public final void clear()
      Description copied from interface: IntPriorityQueue
      Clears the IntPriorityQueue, removing all elements.
      Specified by:
      clear in interface IntPriorityQueue

    • contains

      public final boolean contains(int element)
      Checks if an element is in the IntPriorityQueue.
      Specified by:
      contains in interface IntPriorityQueue
      Parameters:
      element - The element to check for containment.
      Returns:
      true if and only if there exists an (element, priority) pair for the specified element.
      Throws:
      IndexOutOfBoundsException - if element is negative, or if element is greater than or equal to the domain n.

    • createMaxHeap

      public static IntBinaryHeap createMaxHeap(int n)
      Initializes an empty max-heap of (int, priority) pairs, such that the domain of the elements are the integers in [0, n).
      Parameters:
      n - The size of the domain of the elements of the max-heap.
      Returns:
      an empty max-heap
      Throws:
      IllegalArgumentException - if n is non-positive

    • createMinHeap

      public static IntBinaryHeap createMinHeap(int n)
      Initializes an empty min-heap of (int, priority) pairs, such that the domain of the elements are the integers in [0, n).
      Parameters:
      n - The size of the domain of the elements of the min-heap.
      Returns:
      an empty min-heap
      Throws:
      IllegalArgumentException - if n is non-positive

    • demote

      public boolean demote(int element, int priority)
      Demotes an element relative to priority order if the element is present in the IntPriorityQueue. For a min-heap, demotion means increasing the element's priority, while for a max-heap, demotion means decreasing its priority. If the element is not in the IntPriorityQueue, or if its new priority is not a demotion, then this method does nothing.
      Specified by:
      demote in interface IntPriorityQueue
      Parameters:
      element - The element whose priority is to change.
      priority - Its new priority.
      Returns:
      true if and only if the IntPriorityQueue changed as a consequence of this method call.
      Throws:
      IndexOutOfBoundsException - if element is negative, or if element is greater than or equal to the domain n.

    • domain

      public final int domain()
      Description copied from interface: IntPriorityQueue
      Returns the domain of this IntPriorityQueue. Note that the domain is not the same thing as the size. The domain defines the elements that are allowed in the IntPriorityQueue, whether or not they actually appear within it.
      Specified by:
      domain in interface IntPriorityQueue
      Returns:
      the domain of this IntPriorityQueue

    • isEmpty

      public final boolean isEmpty()
      Description copied from interface: IntPriorityQueue
      Checks if the IntPriorityQueue is empty.
      Specified by:
      isEmpty in interface IntPriorityQueue
      Returns:
      true if and only if it is empty

    • offer

      public boolean offer(int element, int priority)
      Adds an (element, priority) pair to the IntPriorityQueue with a specified priority, provided the element is not already in the IntPriorityQueue.
      Specified by:
      offer in interface IntPriorityQueue
      Parameters:
      element - The element.
      priority - The priority of the element.
      Returns:
      true if the (element, priority) pair was added, and false if the IntPriorityQueue already contained the element.
      Throws:
      IndexOutOfBoundsException - if element is negative, or if element is greater than or equal to the domain n.

    • peek

      public final int peek()
      Description copied from interface: IntPriorityQueue
      Gets the next element in priority order from this IntPriorityQueue, without removing it. Behavior is undefined if it is empty.
      Specified by:
      peek in interface IntPriorityQueue
      Returns:
      the next element in priority order.

    • peekPriority

      public int peekPriority()
      Description copied from interface: IntPriorityQueue
      Gets the priority of the next element in priority order in the IntPriorityQueue. Behavior is undefined if it is empty.
      Specified by:
      peekPriority in interface IntPriorityQueue
      Returns:
      the priority of the next element in priority order.

    • peekPriority

      public int peekPriority(int element)
      Gets the current priority of a specified element in the IntPriorityQueue. Behavior is undefined if the IntPriorityQueue doesn't contain the element.
      Specified by:
      peekPriority in interface IntPriorityQueue
      Parameters:
      element - the element whose priority is returned
      Returns:
      the current priority of element.
      Throws:
      IndexOutOfBoundsException - if element is negative, or if element is greater than or equal to the domain n.

    • poll

      public final int poll()
      Description copied from interface: IntPriorityQueue
      Gets and removes the next element in priority order from this IntPriorityQueue. Behavior is undefined if it is empty.
      Specified by:
      poll in interface IntPriorityQueue
      Returns:
      the next element in priority order.

    • promote

      public boolean promote(int element, int priority)
      Promotes an element relative to priority order if the element is present in the IntPriorityQueue. For a min-heap, promotion means decreasing the element's priority, while for a max-heap, promotion means increasing its priority. If the element is not in the IntPriorityQueue, or if its new priority is not a promotion, then this method does nothing.
      Specified by:
      promote in interface IntPriorityQueue
      Parameters:
      element - The element whose priority is to change.
      priority - Its new priority.
      Returns:
      true if and only if the IntPriorityQueue changed as a consequence of this method call.
      Throws:
      IndexOutOfBoundsException - if element is negative, or if element is greater than or equal to the domain n.

    • size

      public final int size()
      Description copied from interface: IntPriorityQueue
      Gets the current size of the IntPriorityQueue, which is the number of (element, priority) pairs that it contains.
      Specified by:
      size in interface IntPriorityQueue
      Returns:
      the current size of the IntPriorityQueue.