What is a Heap?

An introduction to the basics of “heaps” and its uses, property, and implementation in C#.

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 the 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 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, then it is the left child of its parent.

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