Package de.bsommerfeld.pathetic.engine.pathfinder.heap.impl

Class PrimitiveMinHeap

java.lang.Object
de.bsommerfeld.pathetic.engine.pathfinder.heap.impl.PrimitiveMinHeap
All Implemented Interfaces:
MinHeap, Resizable, Siftable
public class PrimitiveMinHeap extends Object implements MinHeap, Siftable, Resizable
A highly optimized, array-backed binary min-heap for A* pathfinding.

This implementation provides MinHeap contract with additional optimizations:

  • Guarantees zero object allocations during runtime (hot-path).
  • Uses primitive arrays for perfect CPU cache locality.
  • Supports O(log n) decreaseKey operations via an internal lookup map.
  • Automatically resizes when capacity is exceeded (see Resizable).
  • Uses 1-based indexing internally for efficient parent/child calculations.

Implements Siftable for heap property maintenance through sift operations.

Since:
5.4.1
See Also:

  • Constructor Summary

    Constructors
    Constructor
    Description
    PrimitiveMinHeap(int initialCapacity)
     

  • Method Summary

    Modifier and Type
    Method
    Description
    int
    capacity()
    Returns the current capacity of the internal storage.
    void
    clear()
    Removes all elements from the heap.
    boolean
    contains(long packedNode)
    Checks if a specific node is currently in the heap.
    double
    cost(long packedNode)
    Gets the current cost of a node in the heap.
    void
    ensureCapacity()
    Ensures the internal storage has sufficient capacity, resizing if necessary.
    long
    extractMin()
    Removes and returns the node with the minimum cost from the heap.
    void
    insertOrUpdate(long packedNode, double cost)
    Inserts a new node or updates an existing node's cost in the heap.
    boolean
    isEmpty()
    Checks if the heap is empty.
    void
    siftDown(int index)
    Moves a node down the heap until the heap property is restored.
    void
    siftUp(int index)
    Moves a node up the heap until the heap property is restored.
    int
    size()
    Returns the number of elements currently in the heap.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • PrimitiveMinHeap

      public PrimitiveMinHeap(int initialCapacity)
      Parameters:
      initialCapacity - The initial size of the heap. Pro-tip: Set this to ~1.5x expected path length to avoid resizing.

  • Method Details

    • isEmpty

      public boolean isEmpty()
      Description copied from interface: MinHeap
      Checks if the heap is empty.
      Specified by:
      isEmpty in interface MinHeap
      Returns:
      true if the heap contains no elements, false otherwise

    • size

      public int size()
      Description copied from interface: MinHeap
      Returns the number of elements currently in the heap.
      Specified by:
      size in interface MinHeap
      Returns:
      the size of the heap

    • clear

      public void clear()
      Description copied from interface: MinHeap
      Removes all elements from the heap.
      Specified by:
      clear in interface MinHeap

    • contains

      public boolean contains(long packedNode)
      Description copied from interface: MinHeap
      Checks if a specific node is currently in the heap.
      Specified by:
      contains in interface MinHeap
      Parameters:
      packedNode - the node identifier (e.g., packed coordinate or node ID)
      Returns:
      true if the node is present in the heap, false otherwise

    • cost

      public double cost(long packedNode)
      Description copied from interface: MinHeap
      Gets the current cost of a node in the heap.
      Specified by:
      cost in interface MinHeap
      Parameters:
      packedNode - the node identifier
      Returns:
      the cost associated with the node, or Double.MAX_VALUE if not present

    • insertOrUpdate

      public void insertOrUpdate(long packedNode, double cost)
      Description copied from interface: MinHeap
      Inserts a new node or updates an existing node's cost in the heap.

      If the node is not currently in the heap, it is inserted with the given cost. If the node already exists and the new cost is lower, the node's cost is updated (decrease-key operation).

      Specified by:
      insertOrUpdate in interface MinHeap
      Parameters:
      packedNode - the unique identifier of the node
      cost - the cost associated with the node (typically F-cost for A*)

    • extractMin

      public long extractMin()
      Description copied from interface: MinHeap
      Removes and returns the node with the minimum cost from the heap.
      Specified by:
      extractMin in interface MinHeap
      Returns:
      the identifier of the node with the minimum cost

    • capacity

      public int capacity()
      Description copied from interface: Resizable
      Returns the current capacity of the internal storage.
      Specified by:
      capacity in interface Resizable
      Returns:
      the total capacity before resizing is needed

    • ensureCapacity

      public void ensureCapacity()
      Description copied from interface: Resizable
      Ensures the internal storage has sufficient capacity, resizing if necessary.
      Specified by:
      ensureCapacity in interface Resizable

    • siftUp

      public void siftUp(int index)
      Description copied from interface: Siftable
      Moves a node up the heap until the heap property is restored.

      Used after inserting a new node or decreasing a node's cost.

      Specified by:
      siftUp in interface Siftable
      Parameters:
      index - the starting position of the node to sift up

    • siftDown

      public void siftDown(int index)
      Description copied from interface: Siftable
      Moves a node down the heap until the heap property is restored.

      Used after removing the minimum element or increasing a node's cost.

      Specified by:
      siftDown in interface Siftable
      Parameters:
      index - the starting position of the node to sift down