Analogue of priority queue

Development Programming & Scripting C++
, , ,
7

For people finding this now, there’s (in my opinion) a better way to do it via overriding the < operator and wrapping a TArray up a bit.

Keep in mind: A lower number means higher priority

CODE

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

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