Created
July 4, 2023 04:33
-
-
Save intaxwashere/88a77c1afa801ab8f17421715112961b to your computer and use it in GitHub Desktop.
Priority queue
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * A templated class for a priority queue implementation. | |
| * The priority queue is a data structure that works like a standard queue but each element has a priority. | |
| * The elements will be processed based on their priority (given by a comparison function), not based on their insertion order in the queue. | |
| * Specifically, this priority queue uses a binary heap data structure. | |
| */ | |
| template<typename Type> | |
| class IntaxPriorityQueue | |
| { | |
| using ComparatorType = bool(*)(const Type&, const Type&); | |
| IntaxPriorityQueue() | |
| : Comparator(nullptr) | |
| { | |
| } | |
| IntaxPriorityQueue(ComparatorType Comparator) | |
| : Comparator(Comparator) | |
| { | |
| } | |
| void AssignComparator(ComparatorType Comparator) | |
| { | |
| this->Comparator = Comparator; | |
| } | |
| void Push(const Type& Element) | |
| { | |
| Array.Add(Element); | |
| HeapifyUp(Array.Num() - 1); | |
| } | |
| void HeapifyUp(int32 Index) | |
| { | |
| if (Index == 0) | |
| { | |
| return; | |
| } | |
| int32 ParentIndex = GetParentIndex(Index); | |
| if (Comparator(Array[Index], Array[ParentIndex])) | |
| { | |
| Swap(Index, ParentIndex); | |
| HeapifyUp(ParentIndex); | |
| } | |
| } | |
| void HeapifyDown(int32 Index) | |
| { | |
| int32 LeftChildIndex = GetLeftChildIndex(Index); | |
| int32 RightChildIndex = GetRightChildIndex(Index); | |
| if (LeftChildIndex >= Array.Num()) | |
| { | |
| return; | |
| } | |
| int32 MinIndex = Index; | |
| if (Comparator(Array[LeftChildIndex], Array[Index])) | |
| { | |
| MinIndex = LeftChildIndex; | |
| } | |
| if (RightChildIndex < Array.Num() && Comparator(Array[RightChildIndex], Array[MinIndex])) | |
| { | |
| MinIndex = RightChildIndex; | |
| } | |
| if (MinIndex != Index) | |
| { | |
| Swap(Index, MinIndex); | |
| HeapifyDown(MinIndex); | |
| } | |
| } | |
| void Swap(int32 Index1, int32 Index2) | |
| { | |
| Type Temp = Array[Index1]; | |
| Array[Index1] = Array[Index2]; | |
| Array[Index2] = Temp; | |
| } | |
| Type Pop() | |
| { | |
| Type Element = Array[0]; | |
| Array[0] = Array[Array.Num() - 1]; | |
| Array.RemoveAt(Array.Num() - 1); | |
| HeapifyDown(0); | |
| return Element; | |
| } | |
| Type Peek() const | |
| { | |
| return Array[0]; | |
| } | |
| int32 GetParentIndex(int32 Index) const | |
| { | |
| return (Index - 1) / 2; | |
| } | |
| int32 GetLeftChildIndex(int32 Index) const | |
| { | |
| return Index * 2 + 1; | |
| } | |
| int32 GetRightChildIndex(int32 Index) const | |
| { | |
| return Index * 2 + 2; | |
| } | |
| int32 Num() const | |
| { | |
| return Array.Num(); | |
| } | |
| bool IsEmpty() const | |
| { | |
| return Array.Num() == 0; | |
| } | |
| void Update(const Type& Element) | |
| { | |
| for (int32 i = 0; i < Array.Num(); ++i) | |
| { | |
| if (Array[i] == Element) | |
| { | |
| HeapifyUp(i); | |
| HeapifyDown(i); | |
| break; | |
| } | |
| } | |
| } | |
| private: | |
| TArray<Type> Array; | |
| ComparatorType Comparator; | |
| }; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment