Understanding comparators

A heap data structure is a binary tree that follows the heap property such that the parent node is either greater (max-heap) or smaller (min-heap) than its children. Instances of primitive data types like integers, characters, etc., can be compared to each other using the relational operators < and > to establish the greater and smaller relationships.

However, some problems require us to store more complex data structures like arrays, lists, maps and class objects in a heap. To store anything other than the primitive data types in a heap, we need to define a comparison rule that defines ordering between two items using a comparator.

Working of a comparator

A comparator is a custom function or an object that defines the ordering of items, particularly when there is no natural or default order or we want to override the ordering. In priority queues implemented as heaps, a comparator determines the item with the higher priority between two items.