Tree data structure is used to represent data in hierarchical way that help in organizing data for better access and manipulation. Heap tree is a Complete Binary Tree. It has additional constraint that the any node must have a value less than all its child nodes’ values. Such heap tree with is called a Min Heap.
On the other hand if the heap is created with condition that root of each sub tree must have value greater than or equal to values of its child nodes, it will be called a Max Heap. The relationship is valid between parent and child nodes. The relationship is not between a node and all its decedents.
This definition is recursive. It means that this restriction applies on all the sub-trees of a tree. In other words any sub tree of a Min Heap must follow the condition of lesser value between parent and child nodes. Any sub tree of a Max Heap will follow the condition of greater value between parent and child nodes.
A Min Heap and Max Heap are useful data structures to implement priority queues and implementing efficient sorting algorithms.
Deletion
Deletion takes place at the root node. The last node of the tree takes its place to maintain completeness of the heap. It trickles down to its correct position in Min-Heap after comparisons and interchanges with its child nodes.
Insertion
Insertion takes place at the end of the Min Heap. This is done to maintain completeness of the heap. It moves up to its correct position in Min-Heap after comparisons and interchanges with its parent nodes.
Example- Min Heap
This example is a complete binary tree. It has a root node with value 15. Both its child nodes value 20 and 60 are greater than 15. Node with value 20 has two child nodes with values 25 and 35, both greater than their parent node value. Child nodes of node with value 25 have values 45 and 80, greater than their parent. Child nodes of 60 have values 85 and 65, greater than their parent. This tree satisfies all the conditions for its being called a min Heap
Example- Max Heap
You can carefully examine the following tree to categorize it as a Max- Heap
