Advanced Data Structures: Heaps in C
Heaps are a special type of treebased 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:
 All leaves must be at h or h1 levels for some h > 0. This is known as the complete binary tree property.
 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:
 Increase the heap size by 1.
 Insert the new element at the available position (leftmost position in the last level).
 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;
}
}
}
CCode 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:
 Copy the first element of the heap (root) into some variable.
 Place the last element of the heap in the root’s position.
 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
}
CCode 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)

What is a heap in data structure?
A heap is a special type of binary tree that satisfies the heap property. It is mainly used in algorithms like heap sort and in data structures like priority queues.

What is a max heap and min heap?
In a max heap, the value of a parent node is greater than or equal to the values of its children. In a min heap, the value of a parent node is less than or equal to the values of its children.

How is a heap represented?
A heap is usually represented as an array. The root element is at
Arr[0]
. For any given node at indexi
, its left child is at index2*i + 1
, right child at2*i + 2
and its parent is at index(i1)/2
. 
What is heapify operation?
Heapify is a process of creating a heap from an array. Max heapify is used to create a max heap where as min heapify is used to create a min heap.

What is the time complexity of heap operations?
The time complexity of heap operations like insertion and deletion is O(log n). The time complexity of creating a heap is O(n).

What is the use of heap data structure?
Heap data structure is used in various algorithms like Dijkstra’s algorithm, heap sort, and in data structures like priority queues.

What is the difference between a binary tree and a heap?
A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child. A heap is a complete binary tree that satisfies the heap property.

What is heap sort?
Heap sort is a comparisonbased sorting algorithm that uses a binary heap data structure. It works by building a max heap from the input data, then repeatedly removing the maximum element from the heap and inserting it into an array, which is then sorted.

How to insert an element into a heap?
To insert an element into a heap, you add the element to the end of the array and then sift it up to its proper position.

How to delete an element from a heap?
To delete an element from a heap, you remove the root element, move the last element in the heap to the root, and then sift it down to its proper position.
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!