Two Heaps: Introduction

Let’s go over the Two Heaps pattern, its real-world applications, and some problems we can solve with it.

Overview

As the name suggests, the two heaps pattern uses either two min-heaps, two max-heaps, or a min-heap and a max-heap simultaneously to solve the problem.

Given that there are n elements in a heap, it takes O(logn)O(logn) time to insert an element in it, O(logn)O(logn) time to remove an element from it, and O(1)O(1) time to access the element at the root of the heap. The root stores the smallest element in the case of a min-heap and the largest element in a max-heap.

In some problems, we’re given a set of data such that it can be divided into two parts. We can either use the first part to find the smallest element using the min-heap and the second part to find the largest element using the max-heap, or we can do the reverse and use the first part to find the largest element using the max-heap and the second part to find the smallest element using the min-heap.

There might be cases where we need to find the two largest numbers from two different data sets. We’ll use two max-heaps to store two different data sets in that case. In other cases, we might need to find the two smallest numbers from two different data sets, and then we would use two min-heaps.

Let’s look at the following illustration to understand how we can use heaps to find the smallest or largest number:

Create a free account to view this lesson.

By signing up, you agree to Educative's Terms of Service and Privacy Policy