Download

Made a simple (but useful) Priority Queue/Binary Heap wrapper around TArray

While working on a grid-based game, I figured I’d make my own pathfinding for funsies. But I was missing (or couldn’t find it in the documentation…) a simple Priority Queue/Binary Heap. I did notice that TArray supports some heap-like functionality, so I made a simple wrapper to basically turn it into a very simple heap. It also helps me to not accidentally invalidate the heap while using TArray’s methods.

I figured this might come in handy for some other people as well!

The code’s layout get’s completely butchered on this page… If you want a better formatted one, here’s the link to the gist (that’ll also be updated if need be):



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();
}


Happy programming!