Advanced Data Structures: Heaps in C

Heaps are a special type of tree-based data structure that are an integral part of advanced data structures in C. They are primarily used in implementing priority queues and in sorting algorithms like Heap Sort. In this tutorial, we will delve into the world of heaps, understand their properties, and learn how to implement them in C.

Understanding Heaps

A heap is a complete binary tree that follows two properties:

1. All leaves must be at h or h-1 levels for some h > 0. This is known as the complete binary tree property.
2. The value of the node must be greater than or equal to (in a Max Heap) or less than or equal to (in a Min Heap) the values of its children nodes. This is known as the heap property.

There are two types of heaps:

• Min Heap: In a Min Heap, the value of a node is less than or equal to the values of its children nodes. This means that the smallest element is at the root of the tree.
• Max Heap: In a Max Heap, the value of a node is greater than or equal to the values of its children nodes. This means that the largest element is at the root of the tree.

Implementing Heaps in C

Inserting an Element

Inserting an element in a heap involves the following steps:

1. Increase the heap size by 1.
2. Insert the new element at the available position (leftmost position in the last level).
3. Heapify the element from the bottom to the top (also known as “bubbling up”).

Here’s a simple code snippet that demonstrates how to insert an element in a Max Heap:

void insertHeap(int A[], int *n, int value) {
    *n = *n + 1; // n is incremented to insert the new element
    A[*n] = value; // assign new value at the nth position
    int i = *n; // assign the value of n to i
    int parent;

    // loop will be executed until i becomes 1
    while(i > 1) {
        parent = i / 2; // Calculating the parent value
        // Condition to check whether the value of parent is less than the given node or not
        if(A[parent] < A[i]) {
            swap(&A[parent], &A[i]);
            i = parent;
        } else {
            return;
        }
    }
}

Code Explanation

In the above code, we first increment the size of the heap (n) by 1. Then we insert the new element at the end of the heap. After that, we start a loop that continues until the inserted element is at the root of the heap (i.e., i becomes 1). In each iteration of the loop, we compare the inserted element with its parent. If the inserted element is greater than its parent, we swap them. This process continues until the inserted element is less than or equal to its parent, ensuring the heap property is maintained.

Deleting an Element

Deleting an element from a heap involves the following steps:

1. Copy the first element of the heap (root) into some variable.
2. Place the last element of the heap in the root’s position.
3. Bubble down to make it a valid heap.

Here’s a simple code snippet that demonstrates how to delete an element from a Max Heap:

int deleteHeap(int A[], int *n) {
    int value = A[1]; // Copy the root value into some variable
    A[1] = A[*n]; // Place the last element of the heap in the root's position
    *n = *n - 1; // Decrease the size of the heap by 1
    maxHeapify(A, 1, *n); // Call maxHeapify on the root to make it a valid heap
    return value; // Return the deleted value
}

Code Explanation

In the above code, we first copy the root value into a variable. Then, we replace the root with the last element of the heap and decrease the size of the heap by 1. After that, we call the maxHeapify function on the root to restore the heap property. The maxHeapify function ensures that the root is greater than its children. If not, it swaps the root with its largest child and then recursively heapifies the affected subtree. This process continues until the heap property is restored, i.e., the parent node is larger than its children. Finally, we return the deleted value.

Wrapping Up

Heaps are a powerful data structure that can be used to implement priority queues and sorting algorithms. They provide efficient operations for inserting elements, deleting elements, and finding the minimum or maximum element. With a good understanding of heaps, you can tackle complex problems with ease and write efficient code. Keep practicing and happy coding!

Frequently Asked Questions (FAQ)

Related Tutorials

• Introduction to Data Structures in C
• Trees in C
• Advanced Data Structures: Binary Trees in C
• Advanced Data Structures: Segment Trees in C
• Advanced Data Structures: graphs in C

Remember, understanding heaps is a stepping stone to mastering advanced data structures. Keep learning and exploring!