{"id":746,"date":"2024-10-19T13:51:39","date_gmt":"2024-10-19T08:21:39","guid":{"rendered":"https:\/\/codexplained.in\/?p=746"},"modified":"2025-11-24T15:34:24","modified_gmt":"2025-11-24T10:04:24","slug":"implement-binary-heap","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=746","title":{"rendered":"Implement Binary Heap"},"content":{"rendered":"
\n#include <stdio.h>\n#include <stdlib.h>\n\ntypedef struct {\n    int *array; \/\/ Pointer to the array of heap elements\n    int size;   \/\/ Current size of the heap\n    int capacity; \/\/ Maximum capacity of the heap\n} MaxHeap;\n\n\/\/ Function to create a MaxHeap\nMaxHeap* createHeap(int capacity) {\n    MaxHeap* maxHeap = (MaxHeap*)malloc(sizeof(MaxHeap));\n    maxHeap->capacity = capacity;\n    maxHeap->size = 0;\n    maxHeap->array = (int*)malloc(capacity * sizeof(int));\n    return maxHeap;\n}\n\n\/\/ Function to swap two elements\nvoid swap(int *a, int *b) {\n    int temp = *a;\n    *a = *b;\n    *b = temp;\n}\n\n\/\/ Function to heapify a subtree rooted at index i\nvoid heapify(MaxHeap* maxHeap, int index) {\n    int largest = index; \/\/ Initialize largest as root\n    int left = 2 * index + 1; \/\/ left = 2*i + 1\n    int right = 2 * index + 2; \/\/ right = 2*i + 2\n\n    \/\/ If left child is larger than root\n    if (left < maxHeap->size && maxHeap->array[left] > maxHeap->array[largest]) {\n        largest = left;\n    }\n\n    \/\/ If right child is larger than largest so far\n    if (right < maxHeap->size && maxHeap->array[right] > maxHeap->array[largest]) {\n        largest = right;\n    }\n\n    \/\/ If largest is not root\n    if (largest != index) {\n        swap(&maxHeap->array[index], &maxHeap->array[largest]);\n        heapify(maxHeap, largest); \/\/ Recursively heapify the affected subtree\n    }\n}\n\n\/\/ Function to insert a new key\nvoid insert(MaxHeap* maxHeap, int key) {\n    if (maxHeap->size == maxHeap->capacity) {\n        printf("Heap is full. Cannot insert %d\\n", key);\n        return;\n    }\n\n    \/\/ Insert the new key at the end\n    maxHeap->array[maxHeap->size] = key;\n    maxHeap->size++;\n\n    \/\/ Fix the max heap property if it's violated\n    for (int i = (maxHeap->size \/ 2) - 1; i >= 0; i--) {\n        heapify(maxHeap, i);\n    }\n}\n\n\/\/ Function to delete the maximum element (root)\nint deleteMax(MaxHeap* maxHeap) {\n    if (maxHeap->size <= 0) {\n        return -1; \/\/ Heap is empty\n    }\n    if (maxHeap->size == 1) {\n        maxHeap->size--;\n        return maxHeap->array[0]; \/\/ Only one element left\n    }\n\n    \/\/ Store the maximum value, and remove it from heap\n    int root = maxHeap->array[0];\n    maxHeap->array[0] = maxHeap->array[maxHeap->size - 1];\n    maxHeap->size--;\n    heapify(maxHeap, 0); \/\/ Call heapify on the root\n\n    return root;\n}\n\n\/\/ Function to print the heap\nvoid printHeap(MaxHeap* maxHeap) {\n    for (int i = 0; i < maxHeap->size; i++) {\n        printf("%d ", maxHeap->array[i]);\n    }\n    printf("\\n");\n}\n\n\/\/ Main function to demonstrate the heap operations\nint main() {\n    MaxHeap* maxHeap = createHeap(10);\n\n    \/\/ Inserting elements\n    insert(maxHeap, 3);\n    insert(maxHeap, 1);\n    insert(maxHeap, 14);\n    insert(maxHeap, 7);\n    insert(maxHeap, 9);\n    insert(maxHeap, 10);\n    insert(maxHeap, 4);\n\n    printf("Max Heap: ");\n    printHeap(maxHeap);\n\n    \/\/ Deleting the maximum element\n    printf("Deleted maximum element: %d\\n", deleteMax(maxHeap));\n    printf("Max Heap after deletion: ");\n    printHeap(maxHeap);\n\n    \/\/ Free allocated memory\n    free(maxHeap->array);\n    free(maxHeap);\n    return 0;\n}\n\n<\/pre><\/div>\n\n\n
Code Explanation<\/h3>\n\n\n\n
    \n
  1. Struct Definition<\/strong>: The MaxHeap<\/code> structure contains an array to hold heap elements, the current size, and the maximum capacity of the heap.<\/li>\n\n\n\n
  2. Heap Creation<\/strong>: The createHeap<\/code> function initializes the heap with a specified capacity.<\/li>\n\n\n\n
  3. Swapping Elements<\/strong>: The swap<\/code> function swaps two integers in the heap array.<\/li>\n\n\n\n
  4. Heapifying<\/strong>: The heapify<\/code> function maintains the heap property. It checks if the subtree rooted at the given index follows the max-heap property and corrects it if not.<\/li>\n\n\n\n
  5. Insertion<\/strong>: The insert<\/code> function adds a new key to the heap. If the heap is full, it prints a message. After inserting, it ensures the heap property is maintained.<\/li>\n\n\n\n
  6. Deletion<\/strong>: The deleteMax<\/code> function removes the maximum element from the heap (the root). It replaces the root with the last element, reduces the size, and then heapifies from the root to restore the heap property.<\/li>\n\n\n\n
  7. Printing the Heap<\/strong>: The printHeap<\/code> function outputs the current elements in the heap.<\/li>\n\n\n\n
  8. Main Function<\/strong>: This is where the program starts. It creates a max heap, inserts several elements, prints the heap, deletes the maximum element, and prints the heap again.<\/li>\n<\/ol>\n\n\n\n
    4. Output<\/h3>\n\n\n\n
    When you run the program, you can expect output similar to the following:<\/p>\n\n\n\n
    Max Heap: 14 9 10 3 1 4 7 \nDeleted maximum element: 14\nMax Heap after deletion: 10 9 7 3 1 4 \n<\/code><\/pre>\n\n\n\n
    Conclusion<\/h3>\n\n\n\n
    This implementation covers the basics of a binary heap with insertions and deletions. You can expand upon this by adding more functionalities, such as a function to peek at the maximum element without removing it or implementing a min-heap in a similar manner. This approach provides a solid foundation for understanding binary heaps and their applications in various algorithms.<\/p>\n