Implementation of Heap in C
In C, heaps are typically stored in arrays. This makes them faster to access and modify elements. And due to its completeness, we can easily find the index of the child and parents nodes. Here is how to find child and parent nodes of an element at index i in the array:
- Left child: 2 * i + 1
- Right child: 2 * i + 2
- Parent: (i – 1) / 2
All the values are assuming the index starts from 0.
Heap Representation in C
We can represent heap directly as an array but we will then have to keep the track of the size in another variable and will have to pass this variable as another argument to heap functions. To simplify it, we can create a structure with array and the size variable in it to represent the heap in C.
typedef struct heap {
int size;
int capacity;
int* arr;
} Heap;
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