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

Interface MinHeap

All Known Implementing Classes:
PrimitiveMinHeap, QuaternaryPrimitiveMinHeap
public interface MinHeap
Contract for min-heap implementations used in pathfinding algorithms.

This interface defines the core operations required for efficient pathfinding with A* and similar algorithms. Implementations should provide O(log n) insert/update and extract operations.

Since:
5.4.3

  • Method Summary

    Modifier and Type
    Method
    Description
    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.
    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.
    int
    size()
    Returns the number of elements currently in the heap.

  • Method Details

    • isEmpty

      boolean isEmpty()
      Checks if the heap is empty.
      Returns:
      true if the heap contains no elements, false otherwise

    • size

      int size()
      Returns the number of elements currently in the heap.
      Returns:
      the size of the heap

    • clear

      void clear()
      Removes all elements from the heap.

    • contains

      boolean contains(long nodeId)
      Checks if a specific node is currently in the heap.
      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

      double cost(long nodeId)
      Gets the current cost of a node in the heap.
      Parameters:
      nodeId - the node identifier
      Returns:
      the cost associated with the node, or Double.MAX_VALUE if not present

    • insertOrUpdate

      void insertOrUpdate(long nodeId, double cost)
      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).

      Parameters:
      nodeId - the unique identifier of the node
      cost - the cost associated with the node (typically F-cost for A*)

    • extractMin

      long extractMin()
      Removes and returns the node with the minimum cost from the heap.
      Returns:
      the identifier of the node with the minimum cost