What is a Heap?

In this lesson, we will learn the basics of Heaps and its uses. We will also discuss the Heap property and how a heap is implemented.

We'll cover the following

Introduction

Heaps are advanced data structures that are useful in applications such as sorting and implementing priority queues. They are regular binary trees with two special properties:

  • Heaps must be Complete Binary Trees
  • The nodes must be ordered according to the Heap Order Property

📝 Heaps are binary trees. Therefore, sometimes they are called Binary Heaps.

Heaps must be Complete Binary Trees

As discussed in trees chapter, a complete binary tree is a binary tree in which all the levels of the tree are fully filled, except for perhaps the last level, which can be filled from left to right.

Some Complete Binary Tree Properties:

  1. All leaves are either at depth dd or depth d−1d-1.
  2. The leaves at depth dd are to the left of the leaves at depth d−1d-1.
  3. There is at most one node with just one child.
  4. If the singular child exists, then it is the left child of its parent.

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.