Heap Operations Implementation in C
There are seven basic operations that are needed to work with heap data structure:
Operation Name | Description | Time Complexity | Space Complexity |
---|---|---|---|
Insert | Adds a new element to the heap and maintains the heap property. | O(log n) | O(1) |
Extract Min/Max | Removes and returns the minimum/maximum element from the heap. | O(log n) | O(1) |
Peek | Returns the minimum/maximum element without removing it. | O(1) | O(1) |
Heapify | Reorganizes a subtree for the given node to ensure the heap property holds | O(log n) | O(1) |
Delete | Removes a specific element from the heap. | O(log n) | O(1) |
Increase/Decrease Key | Changes the value of an existing element in the heap. | O(log n) | O(1) |
Build Heap | Converts an array into a proper min or max heap. | O(n) | O(1) |
Heapify Implementation in C
Heapify function is implemented with the function signature: heapify(Heap* heap, int i) where, heap is the pointer to Heap and i is the index on which heapify is called.
- Check if the left child exists.
- If the left child exists and is greater than the current largest node, mark it as largest.
- Check if the right child exists.
- If the right child exists and is greater than the current largest node, mark it as largest
- If the largest node is not the root node, swap the root node with the largest node using the swap function.
- Apply heapify operation to the affected subtree.
Build Heap Implementation in C
- Get the number of elements in the heap.
- Identify the starting point for heapification. The function identifies the last non-leaf node in the heap, which is the parent of the last element. This is calculated as (n – 1) / 2.
- The function then enters a loop that starts from the last non-leaf node and goes up to the root node. Inside the loop, it calls heapify(heap, i) to ensure that the subtree rooted at i is a max heap heapifying all the levels.
Insert Key Implementation in C
- Check if the max heap is full. If it is, print “MaxHeap overflow” and return from the function.
- If the heap is not full, increase the size of the heap by 1.
- Insert the new value at the end of the heap.
- If the newly inserted value is greater than its parent, the max heap property is violated. To fix this, the function enters a loop that continues until i is not 0 and the parent of i is less than i. Inside the loop, it swaps the value at i with its parent and then updates i to be the index of the parent.
Extract Min/Max Implementation in C
- Check if the heap is empty. If it is empty, return INT_MIN/INT_MAX as an indication that the heap is empty.
- Else, store the root value (maximum/minimum value) in temp, replace the root with the last element in the heap, and decrement heap size by 1.
- Call Heapify(Heap, 0) to ensure that the new root is the maximum element in the heap.
- Finally, return temp, which is the extracted maximum value.
Delete Key Implementation in C
- Check if the index is valid. If the index is invalid, print “Invalid index” and return from the function.
- If the element to be deleted is the last element in the heap, simply decrement heap size by 1 and return from the function.
- Move the last element to the index of the element to be deleted.
- Reduce the size of the heap.
- Call heapify(heap, index) to ensure that the subtree rooted at the given index is a heap.
Increase Key Implementation in C
- Check if the index is valid and new value is greater. If it is, print “Invalid index or new value is not greater” and return from the function.
- If the index is valid and the new value is greater, update the value at the given index to the new value.
- If the updated value is greater than its parent, the max heap property is violated. To fix this, the function enters a loop that continues until index is not 0 and the parent of index is less than index. Inside the loop, it swaps the value at index with its parent and then updates index to be the index of the parent.
The decrease key for min heap will also be implemented using the same algorithm.
Heap in C
A heap is a type of tree data structure where each node is either greater than or equal to or is less than or equal to the values of its children. Depending on this, there are two types of heaps:
- Min Heap: Each node is less than or equal to the value of its child subtrees.
- Max Heap: Each node is greater than or equal to the value of its child subtrees.
Apart from this, heap is also a complete tree. It means that all the before the last level have all its children nodes and in the last level, all the children will be filled from left to right.
In this article, we will learn how to implement the heap data structure in C along with its basic operations. We will take binary heap for example. For k-ary heap, please refer to this article – K-ary Heap Data Structure
Contact Us