[ Home Page ] [ Back ] [ Content of Contributions ] [ Movement: Green Leaf World ]
Heap Tree
Definition: A complete binary tree having any one of the following properties.
Either,
Root of every sub-tree having highest value among all values under that sub-tree, called Max-Heap.
Or,
Root of every sub-tree having lowest value among all values under that sub-tree, called Min-Heap.
Representation of Heap Tree
The root value is stored at may be index 0. The left child & right child of ith index are stored in (2i+1) & (2i+2) respectively.
The root value is stored at may be index 1. The left child & right child of ith index are stored in 2i & (2i+1) respectively.
Insert into Heap Tree
Let, H be the array representing a heap. Initially, N is 0. This implies the tree is empty.
Let, the value 25 is to be inserted. The value will be inserted at Nth index to ensure the remains complete binary tree. As, 25 is the only value, it is a heap tree.
Next, insert 32 at the index 1(as N=1) to maintain complete binary tree property of H. Now, calculate the parent of 1, which is 0, Compare H(0) and H(1). Here, H(0) < H(1), which violating the rule of Max-Heap, So Interchange H(0) and H(1). Now, H is again Max-Heap.
Next, insert 45 at the index 2(as N=2) to maintain
complete binary tree property of H. Now, calculate the parent of 2,
which is 0, Compare H(0) and H(2). Here, H(0) < H(2), which violating the rule of Max-Heap, So Interchange H(0) and H(2). Now, H is again Max-Heap.
Next, insert 38 at the index 3(as N=3) to maintain
complete binary tree property of H. Now, calculate the parent of 3,
which is 1, Compare H(1) and H(3). Here, H(1) < H(3), which violating the rule of Max-Heap, So Interchange H(1) and H(3). Now again, calculate the parent of 1,
which is 0, Compare H(0) and H(1). Here, H(0) > H(1), so, H is a Max-Heap.
Next, insert 75 at the index 4(as N=4) to maintain
complete binary tree property of H. Now, calculate the parent of 4,
which is 1, Compare H(1) and H(4). Here, H(1) < H(4), which violating the rule of Max-Heap, So Interchange H(1) and H(4). Now again, calculate the parent of 1,
which is 0, Compare H(0) and H(1). Again, H(0) < H(1), which violating the rule of Max-Heap, So Interchange H(1) and H(0). Now, H is a Max-Heap.Delete from Heap Tree
Only the root of the heap tree can be deleted, but deleting the root node will break the tree into two dis-join sub-tree. To maintain the complete binary tree property, delete the last node, i.e. (N-1)th value and place it in 0th index to delete the root node. But, now the heap property may be violated as happened here. Now, calculate the index of the left child & right child of 0th value, which is 1 & 2, select the largest value among left & right child, here 45 is largest among {45, 32}, Interchange (38, 45). Repeat the process to ensure Max-Heap property for every possible sub-tree.
In both, insert and delete procedure, re-heaping, i.e. rearranging the values by interchanging is very important.
Try Your Own
- Write the algorithm Insert_Max_Heap(H, N, MaxSize, X), where H is an array representing Max-Heap Tree with N number of elements & MaxSize is the size of the array H. X is the new value to be inserted into the Max-Heap Tree represented by the array H.
- Write the algorithm Delete_Max_Heap(H, N, X), where H is an array representing Max-Heap Tree with N number of elements & MaxSize is the size of the array H. X is the deleted value from the Max-Heap Tree represented by the array H.
(You may consult Books for the existing algorithm before writing)
