As we all know, UE does not provide a common container for priority queues.
But there are some heap functions in TArray that can implement priority queue operations.
A simple encapsulation is provided here, in which the smaller the Priority value, the higher the priority.
template<typename ElementType, typename ArrayAllocator = FDefaultAllocator>
class TRFurPriorityQueue
{
public:
FORCEINLINE TRFurPriorityQueue() = default;
FORCEINLINE TRFurPriorityQueue(TRFurPriorityQueue&&) = default;
FORCEINLINE TRFurPriorityQueue(const TRFurPriorityQueue&) = default;
FORCEINLINE TRFurPriorityQueue& operator=(TRFurPriorityQueue&&) = default;
FORCEINLINE TRFurPriorityQueue& operator=(const TRFurPriorityQueue&) = default;
FORCEINLINE bool Pop(bool bAllowShrinking = true);
FORCEINLINE void Empty(bool bAllowShrinking = true);
FORCEINLINE void Enqueue(ElementType&& Item, int32 Priority);
FORCEINLINE void Enqueue(const ElementType& Item, int32 Priority);
FORCEINLINE bool Dequeue(ElementType& OutItem, bool bAllowShrinking = true);
FORCEINLINE int32 Num() const;
FORCEINLINE bool IsEmpty() const;
FORCEINLINE const ElementType* Top() const;
FORCEINLINE bool Top(ElementType& OutItem) const;
private:
struct TNode
{
int32 Priority;
ElementType Element;
FORCEINLINE TNode();
FORCEINLINE TNode(const ElementType& InElement, int32 InPriority);
FORCEINLINE TNode(ElementType&& InElement, int32 InPriority);
};
struct TComparator
{
FORCEINLINE bool operator()(const TNode& A, const TNode& B) const;
};
TArray<TNode> Nodes;
};
template<typename ElementType, typename ArrayAllocator>
FORCEINLINE TRFurPriorityQueue<ElementType, ArrayAllocator>::TNode::TNode()
{ }
template<typename ElementType, typename ArrayAllocator>
FORCEINLINE TRFurPriorityQueue<ElementType, ArrayAllocator>::TNode::TNode(const ElementType& InElement, int32 InPriority)
: Priority(InPriority)
, Element(InElement)
{ }
template<typename ElementType, typename ArrayAllocator>
FORCEINLINE TRFurPriorityQueue<ElementType, ArrayAllocator>::TNode::TNode(ElementType&& InElement, int32 InPriority)
: Priority(InPriority)
, Element(InElement)
{ }
template<typename ElementType, typename ArrayAllocator>
FORCEINLINE bool TRFurPriorityQueue<ElementType, ArrayAllocator>::TComparator::operator()(const TNode& A, const TNode& B) const
{
return A.Priority < B.Priority;
}
template<typename ElementType, typename ArrayAllocator>
FORCEINLINE bool TRFurPriorityQueue<ElementType, ArrayAllocator>::Pop(bool bAllowShrinking)
{
if (IsEmpty())
{
return false;
}
else
{
Nodes.HeapPopDiscard(TComparator(), bAllowShrinking);
return true;
}
}
template<typename ElementType, typename ArrayAllocator>
FORCEINLINE void TRFurPriorityQueue<ElementType, ArrayAllocator>::Empty(bool bAllowShrinking)
{
Nodes.SetNum(0, bAllowShrinking);
}
template<typename ElementType, typename ArrayAllocator>
FORCEINLINE void TRFurPriorityQueue<ElementType, ArrayAllocator>::Enqueue(ElementType&& Item, int32 Priority)
{
Nodes.HeapPush(TNode(Item, Priority), TComparator());
}
template<typename ElementType, typename ArrayAllocator>
FORCEINLINE void TRFurPriorityQueue<ElementType, ArrayAllocator>::Enqueue(const ElementType& Item, int32 Priority)
{
Nodes.HeapPush(TNode(Item, Priority), TComparator());
}
template<typename ElementType, typename ArrayAllocator>
FORCEINLINE bool TRFurPriorityQueue<ElementType, ArrayAllocator>::Dequeue(ElementType& OutItem, bool bAllowShrinking)
{
if (IsEmpty())
{
return false;
}
else
{
OutItem = Nodes.HeapTop().Element;
Nodes.HeapPopDiscard(TComparator(), bAllowShrinking);
return true;
}
}
template<typename ElementType, typename ArrayAllocator>
FORCEINLINE int32 TRFurPriorityQueue<ElementType, ArrayAllocator>::Num() const
{
return Nodes.Num();
}
template<typename ElementType, typename ArrayAllocator>
FORCEINLINE bool TRFurPriorityQueue<ElementType, ArrayAllocator>::IsEmpty() const
{
return Num() == 0;
}
template<typename ElementType, typename ArrayAllocator>
FORCEINLINE const ElementType* TRFurPriorityQueue<ElementType, ArrayAllocator>::Top() const
{
return IsEmpty() ? nullptr : &Nodes.HeapTop().Element;
}
template<typename ElementType, typename ArrayAllocator>
FORCEINLINE bool TRFurPriorityQueue<ElementType, ArrayAllocator>::Top(ElementType& OutItem) const
{
if (IsEmpty())
{
return false;
}
else
{
OutItem = Nodes.HeapTop().Element;
return true;
}
}