Heap is a special case of balanced binary tree data structure where the root-node key is compared with its children and arranged accordingly. If α has child node β then −
key(α) ≥ key(β)
As the value of parent is greater than that of child, this property generates Max Heap. Based on this criteria, a heap can be of two types
Min-Heap: Where the value of the root node is less than or equal to either of its children.
Max-Heap: Where the value of the root node is greater than or equal to either of its children.
Both trees are constructed using the same input and order of arrival.
We shall use the same example to demonstrate how a Max Heap is created. The procedure to create Min Heap is similar but we go for min values instead of max values.
We are going to derive an algorithm for max heap by inserting one element at a time. At any point of time, heap must maintain its property. While insertion, we also assume that we are inserting a node in an already heapified tree.
Note : In Min Heap construction algorithm, we expect the value of the parent node to be less than that of the child node.
Let's understand Max Heap construction by an animated illustration. We consider the same input sample that we used earlier.
Let us derive an algorithm to delete from max heap. Deletion in Max (or Min) Heap always happens at the root to remove the Maximum (or minimum) value.