Operations on Binary Heap in C
Binary Heaps are optimised for the tasks that need to frequently find the maximum and minimum elements from the dataset. The common operations on binary heap are:
| S. No | Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|---|
| 1 | Insert | Adds a new element to the heap and maintains heap property. | O(log n) | O(1) |
| 2 | Extract Min/Max | Removes and returns the maximum/minimum element from the heap | O(log n) | O(1) |
| 3 | Peek | Returns the maximum element without removing it | O(1) | O(1) |
| 4 | Heapify | Maintains the heap property for a particular node and its branch. | O(log n) | O(1) |
| 5 | Delete | Removes an element at a given index and maintains heap property | O(log n) | O(1) |
| 6 | Increase/Decrease Key | Increase/Decrease the value of the already present element. | O(log n) | O(1) |
7 | Build Heap | Creates a heap from an array | O(log n) | O(1) |
Algorithm for Heapify in Min Heap
Heapify(array, size, i):
1. Set i as the largest index.
2. Calculate left child index: leftChild = 2*i + 1
3. Calculate right child index: rightChild = 2*i + 2
4. If leftChild is within the array bounds and array[leftChild] > array[largest]:
- Set leftChild as the largest index.
5. If rightChild is within the array bounds and array[rightChild] > array[largest]:
- Set rightChild as the largest index.
6. If largest is not equal to i:
- Swap array[i] and array[largest].
- Recursively call Heapify on the subtree rooted at the new largest index.
Algorithm for Building Heap using Array
It is process of creating heap data structure from a binary tree. It is used to create min or max heap. Here, we will see some steps for Heapify function
1. Consider an input array as
2. Consider it as a binary tree,
3. Apply Heapify to all the nodes from (n – 1) / 2 node to root node.
4. We get the binary tree.
Algorithm for Insertion in Min Heap
1. If the heap is empty:
- Create a new node as the root.
2. Otherwise (a node is already present):
- Insert the new node at the end (last node from left to right).
3. Heapify the array
Algorithm for Deletion in Min Heap
1. If nodeToBeDeleted is the leafNode:
- remove the node
2. Else swap nodeToBeDeleted with the lastLeafNode:
- remove noteToBeDeleted
3. heapify the array
1. Select element to be deleted
2. Swap it with last element
3. Remove last element
4. Heapify the tree
Algorithm for Peak in Min/Max Heap
This operation returns the maximum value from Max Heap and minimum value from Min Heap without deleting the node.
return arr[0]
C Program to Implement Binary Heap
Binary heaps are the most fundamental data structures which are used in various algorithms. They are mostly used in implementing priority queues and also in heapsort. They are tree-based data structures that satisfy heap order property. In this article, we will study the implementation of Binary heaps in C language.
Contact Us