Heap Flashcards
What is heap ?
A Heap is a Tree-based data structure, which satisfies the below properties:
1- A Heap is a complete tree (All levels are completely filled except possibly the last level and the last level has all keys as left as possible).
2- A Heap is either Min Heap or Max Heap. In a Min-Heap, the key at root must be minimum among all keys present in the Binary Heap. The same property must be recursively true for all nodes in the Tree. Max Heap is similar to MinHeap.
What is binary heap ?
A Binary Heap is a heap where each node can have at most two children. In other words, a Binary Heap is a complete Binary Tree satisfying the above-mentioned properties.
what is min heap. Explain with example
A min-heap is a binary heap data structure where the value of the root node is always the smallest among all nodes. It satisfies the heap property:
- For every node ( i ):
- ( A[i] \leq A[2i + 1] ) (left child)
- ( A[i] \leq A[2i + 2] ) (right child)
This property ensures that the smallest element is always at the root of the tree, which allows for efficient retrieval.
Characteristics of Min-Heap:
1. Binary Tree Representation: It is usually implemented using arrays, where:
- Parent index: ( i )
- Left child index: ( 2i + 1 )
- Right child index: ( 2i + 2 )
2. Complete Binary Tree: All levels are filled except possibly the last, which is filled from left to right.
Operations:
- Insertion: Add the element to the end and “heapify up” to maintain the min-heap property.
- Deletion (Min-Element): Replace the root with the last element, remove it, and “heapify down.”
- Peek Minimum: Always ( O(1) ), as the root contains the smallest element.
Example:
Consider the array: ([3, 5, 9, 6, 8, 20, 10, 12, 18, 9])
Min-Heap Construction:
After inserting elements step-by-step and applying the heap property, the resulting min-heap is:
3
/ \
5 9
/ \ / \
6 8 20 10
/ \
12 18
Array Representation:
The heap can also be represented as an array:
[ 3, 5, 9, 6, 8, 20, 10, 12, 18, 9 ]
Example Operations:
1. Insert 2:
- Add 2 at the end.
- “Heapify up” → Swap 2 with 6, then 2 with 3.
- Resulting heap: [ 2, 5, 3, 6, 8, 20, 10, 12, 18, 9 ].
-
Delete Min:
- Remove 3 (root), replace it with 9.
- “Heapify down” → Swap 9 with 5.
- Resulting heap: [ 5, 6, 9, 12, 8, 20, 10, 9, 18 ].
Applications:
- Priority Queues: Efficient retrieval of the smallest element.
- Heap Sort: Sorting elements in ( O(n \log n) ).
- Graph Algorithms: Prim’s and Dijkstra’s algorithms.
Example of max heap ?
How to represent binary heap ?
Since a Binary Heap is a complete Binary Tree, it can be easily represented using Arrays.
what is the index of root of binary heap is ?
0
which index returns the parent of the heap
Arr[(i-1)/2] Returns the parent node
which index returns the left child node ?
Arr[(2*i)+1] Returns the left child node
which index returns the right child node ?
Arr[(2*i)+2] Returns the right child node
How to get the max element in a max heap. approach only
Getting Maximum Element: In a Max-Heap, the maximum element is always present at the root node which is the first element in the array used to represent the Heap. So, the maximum element from a max heap can be simply obtained by returning the root node as Arr[0] in O(1) time complexity.
How to get the min element in a min heap. approach only
Getting Minimum Element: In a Min-Heap, the minimum element is always present at the root node which is the first element in the array used to represent the Heap. So, the minimum element from a minheap can be simply obtained by returning the root node as Arr[0] in O(1) time complexity.
what do you mean by Heapifying an Element
Generally, on inserting a new element onto a Heap, it does not satisfy the property of Heap as stated above on its own. The process of placing the element at the correct location so that it satisfies the Heap property is known as Heapify.
How to heapify a heap into a max heap ? approach only
Heapifying in a Max Heap: The property of Max Heap says that every node’s value must be greater than the values of its children nodes. So, to heapify a particular node swap the value of the node with the maximum value of its children nodes and continue the process until all of the nodes below it satisfies the Heap property.
What is the time complexity to heapify a tree ?
Time Complexity: The time complexity to heapify a single node is O(h), where h is equal to log(N) in a complete binary tree where N is the total number of nodes.
What is extract min in min heap ?
it means deleting or returning the root of the tree in a min heap
Algorithm for Root Deletion (Or Extract Min in Min Heap):
Since deleting an element at any intermediary position in the heap can be costly, so we can simply replace the element to be deleted by the last element and delete the last element of the Heap.
Replace the root or element to be deleted by the last element.
Delete the last element from the Heap.
Since, the last element is now placed at the position of the root node. So, it may not follow the heap property. Therefore, heapify the last node placed at the position of root.
Implementation of root deletion in a min heap
include
Since deleting an element at any intermediary position in the heap can be costly, so we can simply replace the element to be deleted by the last element and delete the last element of the Heap.
Replace the root or element to be deleted by the last element.
Delete the last element from the Heap.
Since, the last element is now placed at the position of the root node. So, it may not follow the heap property. Therefore, heapify the last node placed at the position of root.
// C++ program for implement deletion in Heaps
using namespace std;
// To heapify a subtree rooted with node i which is
// an index in arr[]. N is size of heap
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i) {
swap(arr[i], arr[largest]);
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
// Function to delete the root from Heap
void deleteRoot(int arr[], int& n)
{
// Get the last element
int lastElement = arr[n - 1];
// Replace root with first element
arr[0] = lastElement;
// Decrease size of heap by 1
n = n - 1;
// heapify the root node
heapify(arr, n, 0);
}
/* A utility function to print array of size n */
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << "\n";
}
// Driver Code
int main()
{
// Array representation of Max-Heap
// 10
// / \
// 5 3
// / \
// 2 4
int arr[] = { 10, 5, 3, 2, 4 };
int n = sizeof(arr) / sizeof(arr[0]); deleteRoot(arr, n); printArray(arr, n); return 0; }
Output:
5 4 3 2
Implementation of root deletion in a min heap
Write the code for the initialization of largest, left and right variables
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2i + 1
int r = 2 * i + 2; // right = 2i + 2
Implementation of root deletion in a min heap
Write the code If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
Implementation of root deletion in a min heap
Write the code If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
Implementation of root deletion in a min heap
Write code If largest is not root
if (largest != i) {
swap(arr[i], arr[largest]);
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
Write the Function to delete the root from Heap
void deleteRoot(int arr[], int& n)
{
// Get the last element
int lastElement = arr[n - 1];
// Replace root with first element
arr[0] = lastElement;
// Decrease size of heap by 1
n = n - 1;
// heapify the root node
heapify(arr, n, 0);
}
How to insert in a heap ? approach only.
Process of Insertion: Elements can be isnerted to the heap following a similar approach as discussed above for deletion. The idea is to:
First increase the heap size by 1, so that it can store the new element.
Insert the new element at the end of the Heap.
This newly inserted element may distort the properties of Heap for its parents. So, in order to keep the properties of Heap, heapify this newly inserted element following a bottom-up approach.
Implementation of insertion of a element in a heap
define MAX 1000 // Max size of Heap
Process of Insertion: Elements can be isnerted to the heap following a similar approach as discussed above for deletion. The idea is to:
First increase the heap size by 1, so that it can store the new element.
Insert the new element at the end of the Heap.
This newly inserted element may distort the properties of Heap for its parents. So, in order to keep the properties of Heap, heapify this newly inserted element following a bottom-up approach.
// C++ program to insert new element to Heap
#include using namespace std;
// Function to heapify ith node in a Heap
// of size n following a Bottom-up approach
void heapify(int arr[], int n, int i)
{
// Find parent
int parent = (i - 1) / 2;
if (parent >= 0) {
// For Max-Heap
// If current node is greater than its parent
// Swap both of them and call heapify again
// for the parent
if (arr[i] > arr[parent]) {
swap(arr[i], arr[parent]);
// Recursively heapify the parent node
heapify(arr, n, parent);
}
}
}
// Function to insert a new node to the Heap
void insertNode(int arr[], int& n, int Key)
{
// Increase the size of Heap by 1
n = n + 1;
// Insert the element at end of Heap
arr[n - 1] = Key;
// Heapify the new node following a
// Bottom-up approach
heapify(arr, n, n - 1);
}
// A utility function to print array of size n
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << "\n"; }
// Driver Code
int main()
{
// Array representation of Max-Heap
// 10
// / \
// 5 3
// / \
// 2 4
int arr[MAX] = { 10, 5, 3, 2, 4 };
int n = 5; int key = 15; insertNode(arr, n, key);
printArray(arr, n);
// Final Heap will be:
// 15
// / \
// 5 10
// / \ /
// 2 4 3
return 0;
}
