A simple Priority Queue (Binary Heap) wrapper for UE4's TArray (for example for A*/A star and Greedy graph traversal)

PriorityQueue.cpp

template <typename InElementType>
struct TPriorityQueueNode {
    InElementType Element;
    float Priority;

    TPriorityQueueNode()
    {
    }

    TPriorityQueueNode(InElementType InElement, float InPriority)
    {
        Element = InElement;
        Priority = InPriority;
    }

    bool operator<(const TPriorityQueueNode<InElementType> Other) const
    {
        return Priority < Other.Priority;
    }
};

template <typename InElementType>
class TPriorityQueue {
public:
    TPriorityQueue()
    {
        Array.Heapify();
    }

public:
    // Always check if IsEmpty() before Pop-ing!
    InElementType Pop()
    {
        TPriorityQueueNode<InElementType> Node;
        Array.HeapPop(Node);
        return Node.Element;
    }

    TPriorityQueueNode<InElementType> PopNode()
    {
        TPriorityQueueNode<InElementType> Node;
        Array.HeapPop(Node);
        return Node;
    }

    void Push(InElementType Element, float Priority)
    {
        Array.HeapPush(TPriorityQueueNode<InElementType>(Element, Priority));
    }

    bool IsEmpty() const
    {
        return Array.Num() == 0;
    }

private:
    TArray<TPriorityQueueNode<InElementType>> Array;
};

// -- Usage
// Lower number means higher priority

// -- Construction
TPriorityQueue<UTile*> Frontier;

// -- Adding elements: (element, priority)
Frontier.Push(TargetTile, 0.0f);
Frontier.Push(Grid->At(10, 16), 8.0f);
Frontier.Push(StartTile, 1000.0f);
 
// -- Iteration
while (!Frontier.IsEmpty()) {
    UTile* Current = Frontier.Pop(); // Removes it from the top of the heap
    Current->DoMagic();
}

HeapPop/HeapPush don’t work with custom structs, right? It seems to expect some type of UObject in the Sorting.h

Correct! The built-in TArray only works with UObjects. It's worth considering if you can refactor the custom structs you're using to something inheriting UObjects, the performance implications are quite minimal.

Thanks. I was afraid about performance.