What is a Heap?

A brief introduction to Heaps and their uses. We will also discuss the Heap property and how a heap is implemented.

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

A Complete Binary tree is a tree where each node has at most two children and the nodes at all levels are full, except for the leaf nodes which can be empty.

Some Complete Binary Tree Properties:

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

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