Page 257 - DCAP407_DATA_STRUCTURE

Data Structure

Max Heaps - A max heap is defined as a heap in which the key value in each node is greater than or
equal to the keys at its children, i.e., key (parent) ≥ key (child). The figure 14.1 depicts a max heap. Here,
the root node 8 is greater than its child nodes 7 and 6. Similarly, 7 and 6 are greater than their child
nodes.

Figure14.1: Max Heap

Min Heaps - A min heap is a heap where the key value in each node is lesser than or equal to the keys of
its children i.e., key (parent) ≤ key (child).The figure 14.2 represents a min heap. Here, the root node 4 is
lesser than its child nodes 6 and 5. Similarly, 6 and 5 are lesser than their child nodes.

Figure 14.2: Min Heap

The Shape Requirement of Heaps
The shape requirement of heaps defines that, in a binary tree all its levels must be full except possibly
the last level, where only some rightmost leaves may be missing. This requirement is valid for both max
and min heaps. In figure 14.3, the first tree (i) is a heap, but the second tree (ii) is not, as the tree’s shape
requirement is violated. The tree in the figure 14.3 (i) satisfies the shape requirement, whereas the tree
in the figure 14.3(ii) does not. The node 10 at level 1 of the figure 14.3 (ii) does not have a left child and
therefore violates the shape requirement.

Figure 14.3: Illustration of Heaps

(i) (ii)

250 LOVELY PROFESSIONAL UNIVERSITY