Analogue of priority queue

Development Programming & Scripting C++
, , ,
1

Question is very simple: is there analogue of std::priority_queue in UE4?

2

Hi,

There isn’t a direct analogue to std::priority_queue, but you can use heap functions on TArray instead, with an inverted predicate:

struct MyType
{
    explicit MyType(int32 InPriority);

    int32 Priority;
};

struct MyTypePredicate
{
    bool operator()(const MyType& A, const MyType& B) const
    {
        // Inverted compared to std::priority_queue - higher priorities float to the top
        return A.Priority > B.Priority;
    }
};

TArray<MyType> Queue;
Queue.HeapPush(MyType(10), MyTypePredicate());
Queue.HeapPush(MyType(5),  MyTypePredicate());
Queue.HeapPush(MyType(20), MyTypePredicate());
Queue.HeapPush(MyType(15), MyTypePredicate());

MyType Next;
Queue.HeapPop(Next, MyTypePredicate());
check(Next.Priority == 20);

Hope this helps,

Steve

4 Likes
3

Thank you!

4

thanks for this

5

Nice solution!! but i have one question is this thread safe for a scenario of one consumer and many producers?

6

I’m afraid not. You’ll need to protect access to the array by a mutex.

Steve

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