What is a Heap?


Heaps are advanced data structures that are useful in applications where you want to sort and implement 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 70+ hands-on prep courses.