[Data Structures] C++ Priority Queue with Custom Comparator

Priority Queues

Priority queues are a special data structure. They're backed by heaps (a type of binary tree), but are used like queues.

What makes a priority queue better than an ordinary queue is that the priority queue will maintain sorted order in O(logN) time even while inserting or removing new elements.

The easiest way to use a priority queue is with primitive data types, such as integers and strings. However,  it's possible to use priority queues on custom types, or to be able to write a custom sorting order for primitive types. 

Custom Comparators

Just like with sorting vectors, it's possible to use a custom comparator with priority queues, which defines how elements in the priority queue are ordered. Traditionally in C++ this is done using a struct, but lambda expressions are quicker to write and also offer the benefit of being able to reference variables outside of its scope (which is tricky to do with structs).

Here's some C++ code that uses a priority queue with a custom comparator, and the custom comparator (which is a lambda expression) is even able to make use of a hash map outside of its scope for its comparisons.

​Like this content and want more? Feel free to look around and find another blog post that interests you. You can also contact me through one of the various social media channels. 

Twitter: @srcmake
Discord: srcmake#3644
Youtube: srcmake
Twitch: www.twitch.tv/srcmake
​Github: srcmake