Operations on Binary Heaps
The common operation involved using heaps are:
- Heapify: Process to rearrange the heap in order to maintain heap-property.
- Insertion: Add a new item in the heap.
- Deletion: Delete an item from the heap.
- Find-max (or Find-min): find a maximum item of a max-heap, or a minimum item of a min-heap, respectively.
1. Heapify:
It is the process to rearrange the elements to maintain the property of heap data structure. It is done when a certain node creates an imbalance in the heap due to some operations on that node. It takes O(log N) to balance the tree.
2. Insertion:
If we insert a new element into the heap since we are adding a new element into the heap so it will distort the properties of the heap so we need to perform the heapify operation so that it maintains the property of the heap. This operation also takes O(logN) time.
Example :
Assume initially heap(taking max-heap) is as follows
8
/ \
4 5
/ \
1 2Now if we insert 10 into the heap
8
/ \
4 5
/ \ /
1 2 10After heapify operation final heap will be look like this
10
/ \
4 8
/ \ /
1 2 5
3. Deletion:
If we delete the element from the heap it always deletes the root element of the tree and replaces it with the last element of the tree. Since we delete the root element from the heap it will distort the properties of the heap so we need to perform heapify operations so that it maintains the property of the heap. It takes O(logN) time.
Example:
Assume initially heap(taking max-heap) is as follows
15
/ \
5 7
/ \
2 3Now if we delete 15 into the heap it will be replaced by leaf node of the tree for temporary.
3
/ \
5 7
/
2After heapify operation final heap will be look like this
7
/ \
5 3
/
2
4. Find-max (or Find-min):
It finds the maximum element or minimum element for max-heap and min-heap respectively and as we know minimum and maximum elements will always be the root node itself for min-heap and max-heap respectively. It takes O(1) time.
Algorithm for building a Heap of an input array A:
BUILD-HEAP(A)
heapsize := size(A);
for i := floor(heapsize/2) downto 1
do HEAPIFY(A, i);
end for
END
A quick look over the above algorithm suggests that the running time is O(n*log(n)) since each call to Heapify costs O(log(n)) and and Build-Heap makes O(n) such calls but this upper bound, though correct, is not asymptotically tight.
We can derive a tighter bound by observing that the running time of Heapify depends on the height of the tree ‘h’ (which is equal to log(n), where n is a number of nodes) and the heights of most sub-trees are small.. Line-3 of Build-Heap runs a loop from the index of the last internal node (heapsize/2) to the index of root(1) . Hence, Heapify takes a different time for each node, which is:
For finding the Time Complexity of building a heap, we must know the number of nodes having height h. For this we use the fact that, A heap of size n has at most nodes with height h.
To derive the time complexity, we express the total cost of Build-Heap as-
Step 2 uses the properties of the Big-Oh notation to ignore the ceiling function and the constant . Similarly in Step three, the upper limit of the summation can be increased to infinity since we are using Big-Oh notation. Sum of infinite G.P. (x < 1)
On differentiating both sides and multiplying by x, we get
Putting the result obtained in (3) back in our derivation (1), we get
Hence Proved that the Time complexity for Building a Binary Heap is .
Binary Heap Notes for GATE Exam [2024]Time Complexity of building a heap:
In the GATE Exam, understanding binary heaps is like having a secret weapon. Questions might ask you to pick the right tool for a job, and heaps are often the superheroes of quick and efficient data organization.
Table of Content
- Introduction to Heap:
- Types of heaps:
- Representation of Binary Heap:
- Operations on Binary Heaps:
- Advantages of Heap Data Structure:
- Disadvantages of Heap Data Structure:
- Previously Asked GATE Questions on Binary Heap