Introduction
Heap stands for a collection of things. There can be a heap of bags, clothes, etc. In programming, a heap is a data structure which is a complete binary tree.
A complete binary tree is one in which all levels are completely filled except possibly the last level.
Heap data structure is a balanced binary tree data structure where the child node is placed in comparison to the root node and then arranged accordingly.
Heap data structure is the most asked topic in interviews. A variety of questions originate from heaps. Let us understand the concept and implementation of heap data structure in detail.
Types of Heap Data Structure
There are two types of heap data structure
- Max heap - From the name, it becomes very clear that the root node will be greater than the child nodes. All the parent nodes are greater than their respective child nodes. Hence, in a max heap the topmost root node is greater among the child ones.
- Min heap - In a min heap, the root node is smaller than the child nodes. The parent node is smaller than the respective child node. Hence, the topmost root node is the smallest among the child ones.
Operations of Heap Data Structure
Just like every other data structure, the heap data structure also has various operations associated with it. Let us discuss each operation in detail.
Insertion operation
Let us take an array A that has elements as 10, 8, 5, 15. Perform the given steps to form a max heap
- Create a binary tree and add the first element 10 in the tree.
- To add the next element 8, compare it with 10 and if it is greater swap both the values. In this case, no change happens.
- Follow the same step for 5. Fill the tree from left to right.
- In the end, we get 15 which is greater than 8. As we are building a max heap we will swap 15 with 8 to form the max heap.
- Again 15 is greater than 10, so we swap 10 with 15 to form the max heap.
Algorithm for Max Heap Construction
Step 1 −Create a new node at the end of the heap.
Step 2 −Assign a new value to the node.
Step 3 −Compare the value of this child node with its parent.
Step 4 −If the value of the parent is less than the child, then swap them.
Step 5 − Repeat steps 3 & 4 until Heap property holds.
Note:
Comparison is done each time the element is added to the heap data structure.
The number of comparisons is dependent on the height of the tree which turns out to be a time complexity of O(nlogn).
Heapify is a process where we can reduce the number of comparisons where elements are first added to the tree and then goes for comparison. The process to rearrange the elements of a tree in order to maintain the properties of heap data structure is called heapify or heapification. This bottom-up comparison of elements reduces the time complexity of the overall algorithm.
Deletion Operation
Let us take an array A that has elements as 10, 8, 5, 15. Perform the given steps to form deletion operation in the heap data structure.
- Let us say the element to be deleted from the tree is 10.
- Swap the last child of the tree with 10 i.e, swap 10 with 5.
- Remove the last element from the tree.
- Now as the last element is removed, we need to call the heapify function to rearrange the heap elements.
- The tree now holds the properties of max heap and element 10 has been deleted.
CPP Program of Heap Data Structure Implementation
#include <iostream> #include <vector> using namespace std;
void swap(int *a, int *b) // function to swap the node values { int temp = *b; // take temp variable *b = *a; *a = temp; } void heapify(vector<int> &hT, int i) // perform heapification { int size = hT.size(); // calculate the size of the tree int largest = i; int l = 2 * i + 1; // form the left node int r = 2 * i + 2; // form the right node if (l < size && hT[l] > hT[largest]) largest = l; if (r < size && hT[r] > hT[largest]) largest = r;
if (largest != i) { swap(&hT[i], &hT[largest]); // swap the values heapify(hT, largest); } } void insert(vector<int> &hT, int newNum) // perform insertion in the max heap { int size = hT.size(); if (size == 0) { hT.push_back(newNum); // push new node to the tree } else { hT.push_back(newNum); for (int i = size / 2 - 1; i >= 0; i--) { heapify(hT, i); // perform heapify operation } } } void deleteNode(vector<int> &hT, int num) // delete a node in the heap { int size = hT.size(); int i; for (i = 0; i < size; i++) { if (num == hT[i]) break; } swap(&hT[i], &hT[size - 1]);
hT.pop_back(); for (int i = size / 2 - 1; i >= 0; i--) { heapify(hT, i); // perform heapify } } void printArray(vector<int> &hT) // print the array in the form of a tree { for (int i = 0; i < hT.size(); ++i) cout << hT[i] << " "; cout <<"; }
int main() { vector<int> h; // the array insert(h, 10); insert(h, 8); insert(h, 5); insert(h, 15); cout << "Max-Heap array: "; printArray(h); deleteNode(h, 5); cout << "After deleting an element: "; printArray(h); // print the array }
Output:
Max-Heap array: 10 8 5 15
After deleting an element: 15 8 10
C Program of Heap Data Structure Implementation
#include <stdio.h> int size = 0; void swap(int *a, int *b) // function to swap two node values { int temp = *b; // swap with the help of a temp variable *b = *a; *a = temp; } void heapify(int array[], int size, int i) // perform heapify operation { if (size == 1) // size 1 means single element in the heap { printf("Single element in the heap"); } else { int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l < size && array[l] > array[largest]) largest = l; if (r < size && array[r] > array[largest]) largest = r; if (largest != i) { swap(&array[i], &array[largest]); // swap the largest and current arr value heapify(array, size, largest); // call the heapify function } } } void insert(int array[], int newNum) // insertion in a max heap { if (size == 0) { array[0] = newNum; size += 1; // increase the size of the heap } else { array[size] = newNum; size += 1; for (int i = size / 2 - 1; i >= 0; i--) { heapify(array, size, i); // perform heapify } } } void deleteRoot(int array[], int num) // delete an element from the heap { int i; for (i = 0; i < size; i++) { if (num == array[i]) break; }
swap(&array[i], &array[size - 1]); size -= 1; for (int i = size / 2 - 1; i >= 0; i--) { heapify(array, size, i); // perform heapify } } void printArray(int array[], int size) { for (int i = 0; i < size; ++i) printf("%d ", array[i]); printf("); } int main() { int h[10]; insert(h, 10); insert(h, 8); insert(h, 5); insert(h, 15); printf("Max-Heap array: "); printArray(h, size); deleteRoot(h, 5); printf("After deleting an element: "); printArray(h, size); // print the array }
Output:
Max-Heap array: 15 10 5 8
After deleting an element: 15 10 8
Conclusion
- A heap is a tree-based data structure that is in the form of a complete binary tree.
- The max heap has the maximum element at the top of the tree and the child nodes are smaller than the root node.
- The min-heap has the minimum element at the top of the tree and the child nodes are greater than the root node.
- The time complexity to build is O(nlogn) where O(logn) time is taken for the heapify process and O(n) time is taken to build the heap.
- Internally priority queues implement heap data structure as it supports insert(), delete() and extractmax(), decreaseKey() operations in O(logn) time.
Happy Reading!
Reference: Scaler Topics
