A heap is a balanced binary tree that follows just two constraints:

  • The value in any node is less than the value in either of the children. This property is also called the heap property.
  • The tree is as balanced as possible—in the sense that any level is completely filled before a single node is inserted in the next level.

The following figure shows a sample heap:


Figure 1. A sample heap

It would not be really clear until we actually discuss how to insert elements and remove the least element. So let's jump into it.


The first step of insertion is to insert the element in the next available position. The next available position is either ...

Get Java 9 Data Structures and Algorithms now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.