Heap Operations Implementation in C

C Program to Implement Heap Data Structure

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

Similar Reads

C #include #include #include // Structure to represent a Heap (previously MaxHeap) typedef struct Heap { int* array; int size; int capacity; } Heap; // Function to create a heap Heap* createHeap(int capacity) { Heap* heap = (Heap*)malloc(sizeof(Heap)); heap->size = 0; heap->capacity = capacity; heap->array = (int*)malloc(capacity * sizeof(int)); return heap; } // Function to swap two integers void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } // Function to heapify the node at index i void heapify(Heap* heap, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < heap->size && heap->array[left] > heap->array[largest]) largest = left; if (right < heap->size && heap->array[right] > heap->array[largest]) largest = right; if (largest != i) { swap(&heap->array[i], &heap->array[largest]); heapify(heap, largest); } } // Function to build a max heap from an existing array void buildHeap(Heap* heap) { int n = heap->size; // Get the number of elements in the // heap // Start from the last non-leaf node (parent of the last // leaf) and heapify all levels in reverse order for (int i = (n - 1) / 2; i >= 0; i--) heapify(heap, i); } // Function to increase the value at a given index void increaseKey(Heap* heap, int index, int newValue) { if (index >= heap->size || heap->array[index] >= newValue) { printf( "Invalid index or new value is not greater\n"); return; } heap->array[index] = newValue; while (index != 0 && heap->array[(index - 1) / 2] < heap->array[index]) { swap(&heap->array[index], &heap->array[(index - 1) / 2]); index = (index - 1) / 2; } } // Function to insert a new value into the heap void insertHeap(Heap* heap, int value) { if (heap->size == heap->capacity) { printf("Heap overflow\n"); return; } heap->size++; int i = heap->size - 1; heap->array[i] = value; // Fix the heap property if it is violated while (i != 0 && heap->array[(i - 1) / 2] < heap->array[i]) { swap(&heap->array[i], &heap->array[(i - 1) / 2]); i = (i - 1) / 2; } } // Function to extract the root (maximum element) int extractMax(Heap* heap) { if (heap->size <= 0) return INT_MIN; if (heap->size == 1) { heap->size--; return heap->array[0]; } // Store the maximum value, and remove it int root = heap->array[0]; heap->array[0] = heap->array[heap->size - 1]; heap->size--; heapify(heap, 0); return root; } // Function to print the heap void printHeap(Heap* heap) { for (int i = 0; i < heap->size; ++i) printf("%d ", heap->array[i]); printf("\n"); } // Function to delete an element at a given index void deleteKey(Heap* heap, int index) { if (index >= heap->size) { printf("Invalid index\n"); return; } // If the element to be deleted is the last element, // simply reduce size if (index == heap->size - 1) { heap->size--; return; } // Move the last element to the index of the element to // be deleted heap->array[index] = heap->array[heap->size - 1]; heap->size--; // Heapify down to maintain heap property heapify(heap, index); } int main() { Heap* heap = createHeap(10); insertHeap(heap, 3); insertMaxHeap(maxHeap, 2); insertMaxHeap(maxHeap, 15); insertMaxHeap(maxHeap, 5); insertMaxHeap(maxHeap, 4); insertMaxHeap(maxHeap, 45); printf("Max Heap array: "); printHeap(maxHeap); printf("Extracted max value: %d\n", extractMax(maxHeap)); printf("Max Heap array after extraction: "); printHeap(maxHeap); free(maxHeap->array); free(maxHeap); return 0; }...

Tags:

#C-DSA #C Language

Implementation of Heap in C

C Program to Implement Heap Data Structure