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 another position in the same level or the first position in the next level; of course, this applies when there is no vacant position in the existing level.
The second step is to iteratively compare the element with its parent and keep switching until the element is bigger than the parent, thus restoring the constraints. The following figure shows the...