Question

Show that in any subtree of a max-heap, the root of the subtree contains the largest value occurring anywhere in the subtree.

Answer 1

Tree represents the nodes connected by edges.

Binary Tree is a special data structure used for data storage purposes. A binary tree has a special condition that each node can have a maximum of two children. A binary tree has the benefits of both an ordered array and a linked list as search is as quick as in a sorted array and insertion or deletion operation are as fast as in linked list.

Heap data structure is a specialized binary tree-based data structure. Heap is a binary tree with special characteristics. In a heap data structure, nodes are arranged based on their values. A heap data structure sometimes also called as Binary Heap.

There are two types of heap data structures and they are as follows.

1. Max Heap
2. Min Heap

Every heap data structure has the following properties...

Property #1 (Ordering): Nodes must be arranged in an order according to their values based on Max heap or Min heap.

Property #2 (Structural): All levels in a heap must be full except the last level and all nodes must be filled from left to right strictly.

Max Heap

Max heap data structure is a specialized full binary tree data structure. In a max heap nodes are arranged based on node value.

Max heap is a specialized full binary tree in which every parent node contains greater or equal value than its child nodes.

Max Heap Construction Algorithm

Step 1 − Create a new node at the end of heap.

Step 2 − Assign new value to the node.

Step 3 − Compare the value of this child node with its parent.

Step 4 − If value of parent is less than child, then swap them.

Step 5 − Repeat step 3 & 4 until Heap property holds.

Base Notation:

• Use array to store the data.
• Start storing from index 1, not 0.
• For any given node at position i:
• Its Left Child is at [2*i] if available.
• Its Right Child is at [2*i+1] if available.
• Its Parent Node is at [i/2]if available.

Required Proof:

Let the root of the sub-tree be at some position A[i] in the array.

From the max-heap property, A[i] >= A[j=2i], if node i has a left-child

and A[i] >= A[k=2*i + 1], if node i has a right-sub-tree.

But, A[j] >= A[2j], if node j has a left-child

and A[j] >= A[2*j + 1], if node j has a right-sub-tree.

Likewise, A[k ] >= A[2k+1)], if node k has a left-child

and A[k] >= A[2*k +1], if node k has a right-sub-tree.

The argument continues for all children in the sub-tree. Hence A[i], the root of the any sub-tree, is larger than the value of any child in that sub-tree, so it contains the largest value in the sub-tree