Insertion into a Max Heap in Data Structure
Introduction:
When an element is inserted into a Max Heap, it is added to the bottom level of the heap and then, until the heap property is satisfied (that is, the parent is greater than the child), it is swapped with its parent repeatedly. The biggest part is always at the root thanks to this procedure. The temporal complexity is generally O(log n), where n is the number of elements in the heap.
What is Heap?
A heap is a specialized tree-based data structure satisfying the heap property, which means, for every node i (except possibly the root), the parent node's key is greater than or equal to its children's. It can be implemented as complete binary tree. To further grasp the heap data structure, it's important to first understand the binary tree.
How can we structure the nodes of the tree?
There are two types of heaps:
- Minimum heaps
- maximum heaps
Max Heap: The parent node's value exceeds or equals that of its children.
Or
In other terms, the max heap is defined as nodes with values less than or equal to their parent, except for the root node. The mathematical definition is as follows:
A[Parent(i)] >= A[i]
Algorithm of insert operation in the max heap
insertHeap(A, n, value)
{
n=n+1;
A[n]=value;
i = n;
while(i>1)
{
parent= floor value of i/2;
or not
if(A[parent]<A[i])
{
swap(A[parent], A[i]);
i = parent;
}
else
{
return;
}
}
}
Let's use an example to better understand the max heap.
In the picture above, 55 is the parent node, which is greater than both of its children, whereas 11 is the parent of 9 & 8, hence 11 is likewise greater than both of its children. As a result, we can classify the above tree as a max heap tree.
Insertion into the Heap tree
44, 33, 77, 11, 55, 88, 66
Suppose we want to create the maximum heap tree. To create the maximum heap tree, we must consider the following two scenarios:
- To preserve the whole binary tree, we must first insert the element.
- Second, the parent node's value should exceed that of either of its children.
Step 1: First, we add 44 nodes to the tree, as illustrated below.
Benefits and drawbacks of heaps
Benefits:
- Garbage collection operates on heap memory to free up the memory utilized by the object.
- Heaps are adaptable because memory can be added or withdrawn in any sequence.
- Variables can be accessible globally.
- It is useful for determining the minimum and maximum numbers.
Drawbacks:
- In comparison to stacks, heaps take longer to perform.
- Memory management is more difficult with heap memory because it is used globally.
- Heaps often take longer to compute.