A heap is a tree with some special properties. The basic requirement of a heap is that the value of
a node must be > (or <) than the values of its children. This is called heap property. A heap also
has the additional property that all leaves should be at h or h – 1 levels (where h is the height of
the tree) for some h > 0 (complete binary trees). That means heap should form a complete binary
tree (as shown below).
Types of Heaps?
Based on the property of a heap we can classify heaps into two types:
• Min heap: The value of a node must be less than or equal to the values of its
children
• Max heap: The value of a node must be greater than or equal to the values of its
children
Binary Heaps
In binary heap each node may have up to two children. In practice, binary heaps are enough and
we concentrate on binary min heaps and binary max heaps for the remaining discussion.
Representing Heaps: Before looking at heap operations, let us see how heaps can be
represented. One possibility is using arrays. Since heaps are forming complete binary trees, there
will not be any wastage of locations. For the discussion below let us assume that elements are
stored in arrays, which starts at index 0.
source: Data Structures and Algorithms Made Easy in Java - Narasimha Karumanchi
