Heap Data Structure
The Heap data structure is a complete binary tree that satisfies the heap property. The heap property states that the key of each parent node is either greater than or equal to its child nodes (for a max heap), or smaller than or equal to its child nodes (for a min heap).
The heap data structure is commonly used to implement priority queues, which allow quick retrieval of the minimum or maximum element from a collection of elements.
Max Heapify
The Max Heapify operation is used to maintain the heap property in a max heap. It compares the key of a parent node with its two child nodes and swaps the parent node with the child that has the maximum key value, ensuring that the largest element is always at the root of the heap.
Here is an example of the Max Heapify operation in C++:
1#include <iostream>
2using namespace std;
3
4// Function to perform max heapify operation
5void maxHeapify(int arr[], int n, int i) {
6 int largest = i;
7 int l = 2 * i + 1;
8 int r = 2 * i + 2;
9
10 // If left child is larger than root
11 if (l < n && arr[l] > arr[largest])
12 largest = l;
13
14 // If right child is larger than largest so far
15 if (r < n && arr[r] > arr[largest])
16 largest = r;
17
18 // If largest is not root
19 if (largest != i) {
20 swap(arr[i], arr[largest]);
21
22 // Recursively heapify the affected sub-tree
23 maxHeapify(arr, n, largest);
24 }
25}
26
27int main() {
28 int arr[] = {12, 11, 13, 5, 6, 7};
29 int n = sizeof(arr) / sizeof(arr[0]);
30
31 maxHeapify(arr, n, 0);
32
33 cout << "Max Heapified array:\n";
34 for (int i = 0; i < n; i++)
35 cout << arr[i] << " ";
36
37 return 0;
38}The output of the above code would be:
1Max Heapified array:
213 11 12 5 6 7Build Max Heap
The Build Max Heap operation is used to convert an array into a max heap. It iterates over the array from the last non-leaf node to the first element and applies the Max Heapify operation to each node. This operation ensures that the entire array satisfies the heap property.
Here is an example of the Build Max Heap operation in C++:
1#include <iostream>
2using namespace std;
3
4// Function to perform max heapify operation
5void maxHeapify(int arr[], int n, int i) {
6 // max heapify logic here
7}
8
9// Function to convert an array into a max heap
10void buildMaxHeap(int arr[], int n) {
11 // Find the index of the last non-leaf node
12 int startIdx = (n / 2) - 1;
13
14 // Perform reverse level order traversal from the last non-leaf node
15 // and heapify each node
16 for (int i = startIdx; i >= 0; i--) {
17 maxHeapify(arr, n, i);
18 }
19}
20
21int main() {
22 int arr[] = {12, 11, 13, 5, 6, 7};
23 int n = sizeof(arr) / sizeof(arr[0]);
24
25 buildMaxHeap(arr, n);
26
27 cout << "Max Heapified array:\n";
28 for (int i = 0; i < n; i++)
29 cout << arr[i] << " ";
30
31 return 0;
32}The output of the above code would be:
1Max Heapified array:
213 11 12 5 6 7xxxxxxxxxx}using namespace std;// Function to perform max heapify operationvoid maxHeapify(int arr[], int n, int i) { int largest = i; int l = 2 * i + 1; int r = 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 maxHeapify(arr, n, largest); }}// Function to convert an array into a max heapvoid buildMaxHeap(int arr[], int n) { // Index of last non-leaf node