Understanding the comparator pattern
A heap data structure can store primitive data types in their natural order defined by the < and > operators. However, there are some problems that require ordering user-defined datatypes. In most cases, we first need to define the new datatype and then define a comparator to be able to store this datatype in a heap.
The comparator pattern is a classification of problems that can be solved using a heap and a custom comparator.
In this lesson, we will learn more about using the custom comparator technique to solve problems and how to identify a problem as a comparator pattern problem.
The custom compare technique
Consider we are given a set of values in an array, an integer k, a user-defined type, a transformation function t and a function f. The transformation function t transforms the values in the original array to instances of the user-defined type. The goal is to find the aggregate value of f over the top k items from the transformed array.
For this example, consider the generic array of values given below.
A generic array of values.
Liking the course? Check our discounted plans to continue learning.