Package squidpony.squidmath

Class BinaryHeap<T extends BinaryHeap.Node>

java.lang.Object
squidpony.squidmath.BinaryHeap<T>
public class BinaryHeap<T extends BinaryHeap.Node>
extends Object
A binary heap that stores nodes which each have a double value and are sorted either lowest first or highest first. The BinaryHeap.Node class can be extended to store additional information.
Author:
Nathan Sweet

  • Nested Class Summary

    Nested Classes 
    Modifier and Type Class Description
    static class  BinaryHeap.Node
    A binary heap node.

  • Field Summary

    Fields 
    Modifier and Type Field Description
    int size  

  • Constructor Summary

    Constructors 
    Constructor Description
    BinaryHeap()  
    BinaryHeap​(int capacity, boolean isMaxHeap)  

  • Method Summary

    Modifier and Type Method Description
    T add​(T node)
    Adds the node to the heap using its current value.
    T add​(T node, double value)
    Sets the node's value and adds it to the heap.
    void clear()  
    boolean contains​(T node, boolean identity)
    Returns true if the heap contains the specified node.
    boolean equals​(Object obj)  
    int hashCode()  
    boolean isEmpty()
    Returns true if the heap is empty.
    boolean notEmpty()
    Returns true if the heap has one or more items.
    T peek()
    Returns the first item in the heap.
    T pop()
    Removes the first item in the heap and returns it.
    T remove​(T node)  
    void setValue​(T node, double value)
    Changes the value of the node, which should already be in the heap.
    String toString()  

    Methods inherited from class java.lang.Object

    clone, finalize, getClass, notify, notifyAll, wait, wait, wait

  • Field Details

  • Constructor Details

  • Method Details

    • add

      public T add​(T node)
      Adds the node to the heap using its current value. The node should not already be in the heap.

    • add

      public T add​(T node, double value)
      Sets the node's value and adds it to the heap. The node should not already be in the heap.

    • contains

      public boolean contains​(T node, boolean identity)
      Returns true if the heap contains the specified node.
      Parameters:
      identity - If true, == comparison will be used. If false, .equals() comparison will be used.

    • peek

      public T peek()
      Returns the first item in the heap. This is the item with the lowest value (or highest value if this heap is configured as a max heap).

    • pop

      public T pop()
      Removes the first item in the heap and returns it. This is the item with the lowest value (or highest value if this heap is configured as a max heap).

    • remove

      public T remove​(T node)

    • notEmpty

      public boolean notEmpty()
      Returns true if the heap has one or more items.

    • isEmpty

      public boolean isEmpty()
      Returns true if the heap is empty.

    • clear

      public void clear()

    • setValue

      public void setValue​(T node, double value)
      Changes the value of the node, which should already be in the heap.

    • equals

      public boolean equals​(Object obj)
      Overrides:
      equals in class Object

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • toString

      public String toString()
      Overrides:
      toString in class Object