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

Class QuaternaryPrimitiveMinHeap

java.lang.Object
de.bsommerfeld.pathetic.engine.pathfinder.heap.impl.QuaternaryPrimitiveMinHeap
All Implemented Interfaces:
MinHeap, Resizable, Siftable
public class QuaternaryPrimitiveMinHeap extends Object implements MinHeap, Siftable, Resizable
A quaternary (4-ary) min-heap implementation optimized for pathfinding algorithms.

This implementation provides MinHeap contract using a quaternary tree structure. Each node in the heap can have up to 4 children, which reduces the height of the tree compared to a binary heap, resulting in fewer comparisons during sift operations.

The heap maintains three parallel arrays:

  • heap: stores node IDs in heap order
  • costs: stores the corresponding costs for each node
  • idToPos: provides O(1) lookup from node ID to heap position

This implementation uses 0-based indexing and automatically resizes when capacity is exceeded (see Resizable). Implements Siftable for heap property maintenance through sift operations with quaternary parent/child relationships.

Since:
5.4.2
See Also:

  • Constructor Summary

    Constructors
    Constructor
    Description
    QuaternaryPrimitiveMinHeap()
    Constructs a new quaternary min-heap with the default initial capacity.
    QuaternaryPrimitiveMinHeap(int initialCapacity)
    Constructs a new quaternary min-heap with the specified initial capacity.

  • 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 nodeId)
    Checks if a specific node is currently in the heap.
    double
    cost(long nodeId)
    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 nodeId, 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

    • QuaternaryPrimitiveMinHeap

      public QuaternaryPrimitiveMinHeap()
      Constructs a new quaternary min-heap with the default initial capacity.
      Since:
      5.4.2

    • QuaternaryPrimitiveMinHeap

      public QuaternaryPrimitiveMinHeap(int initialCapacity)
      Constructs a new quaternary min-heap with the specified initial capacity.
      Parameters:
      initialCapacity - the initial capacity for the heap
      Since:
      5.4.1

  • Method Details

    • insertOrUpdate

      public void insertOrUpdate(long nodeId, 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:
      nodeId - the unique identifier of the node
      cost - the cost associated with the node (typically F-cost for A*)

    • 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

    • 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 nodeId)
      Description copied from interface: MinHeap
      Checks if a specific node is currently in the heap.
      Specified by:
      contains in interface MinHeap
      Parameters:
      nodeId - 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 nodeId)
      Description copied from interface: MinHeap
      Gets the current cost of a node in the heap.
      Specified by:
      cost in interface MinHeap
      Parameters:
      nodeId - the node identifier
      Returns:
      the cost associated with the node, or Double.MAX_VALUE if not present

    • isEmpty

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

    • 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

    • siftUp

      public void siftUp(int index)
      Moves a node up the heap until the heap property is restored.

      This method is used after inserting a new node or decreasing a node's cost. The node at the given index is compared with its parent and swapped if necessary, continuing until the node is in the correct position.

      In a quaternary heap, the parent of a node at index i is at index (i-1)/4, which is computed efficiently using the unsigned right shift operator >>> 2.

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

    • siftDown

      public void siftDown(int index)
      Moves a node down the heap until the heap property is restored.

      This method is used after removing the minimum element. The node at the given index is compared with its children and swapped with the smallest child if necessary, continuing until the node is in the correct position.

      In a quaternary heap, a node at index i has up to 4 children at indices 4*i+1, 4*i+2, 4*i+3, and 4*i+4. The method finds the child with the minimum cost and swaps if needed. The multiplication by 4 is computed efficiently using left shift: index << 2.

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