Last Updated on June 29, 2022 by Ria Pathak
Binary Max – Heap
A binary max – heap follows two conditions:
- The given tree must be a complete binary tree (All levels are completely filled except the last level which can have nodes as left as possible. It will help in storing the Binary Heap in an array.
- All the nodes must have values greater than or equal to their children nodes. The parent will always have the maximum value in the sub-heap.
Algorithm:
- Initialize an array of size (n + m), where n is the size of given array1 and m is the size of given array2.
- Then, firstly add all the elements from array1 and then add all the elements from array2.
- At last, Apply the MaxHeapify method on the resultant array, to convert the resultant array into max – heap.
Code Implementation
#include <bits/stdc++.h>
using namespace std;
void maxHeapify(int arr[], int n, int idx)
{
if (idx >= n)
return;
int l = 2 * idx + 1;
int r = 2 * idx + 2;
int max;
if (l < n && arr[l] > arr[idx])
max = l;
else
max = idx;
if (r < n && arr[r] > arr[max])
max = r;
if (max != idx) {
swap(arr[max], arr[idx]);
maxHeapify(arr, n, max);
}
}
void buildMaxHeap(int arr[], int n)
{
for (int i = n / 2 - 1; i >= 0; i--)
maxHeapify(arr, n, i);
}
void mergeHeaps(int merged[], int a[], int b[],
int n, int m)
{
for (int i = 0; i < n; i++)
merged[i] = a[i];
for (int i = 0; i < m; i++)
merged[n + i] = b[i];
buildMaxHeap(merged, n + m);
}
int main()
{
int a[] = { 20, 15, 16, 12 };
int b[] = { 22, 17, 19 };
int n = sizeof(a) / sizeof(a[0]);
int m = sizeof(b) / sizeof(b[0]);
int merged[m + n];
mergeHeaps(merged, a, b, n, m);
for (int i = 0; i < n + m; i++)
cout << merged[i] << " ";
return 0;
}
class Prepbytes {
public static void maxHeapify(int[] arr, int n,
int i)
{
if (i >= n) {
return;
}
int l = i * 2 + 1;
int r = i * 2 + 2;
int max;
if (l < n && arr[l] > arr[i]) {
max = l;
}
else
max = i;
if (r < n && arr[r] > arr[max]) {
max = r;
}
if (max != i) {
int temp = arr[max];
arr[max] = arr[i];
arr[i] = temp;
maxHeapify(arr, n, max);
}
}
public static void mergeHeaps(int[] arr, int[] a,
int[] b, int n, int m)
{
for (int i = 0; i < n; i++) {
arr[i] = a[i];
}
for (int i = 0; i < m; i++) {
arr[n + i] = b[i];
}
n = n + m;
for (int i = n / 2 - 1; i >= 0; i--) {
maxHeapify(arr, n, i);
}
}
public static void main(String[] args)
{
int[] a = {20, 15, 16, 12};
int[] b = {22, 17, 19};
int n = a.length;
int m = b.length;
int[] merged = new int[m + n];
mergeHeaps(merged, a, b, n, m);
for (int i = 0; i < m + n; i++)
System.out.print(merged[i] + " ");
System.out.println();
}
}
def MaxHeapify(arr, n, idx): if idx >= n: return l = 2 * idx + 1 r = 2 * idx + 2 Max = 0 if l < n and arr[l] > arr[idx]: Max = l else: Max = idx if r < n and arr[r] > arr[Max]: Max = r if Max != idx: arr[Max], arr[idx] = arr[idx], arr[Max] MaxHeapify(arr, n, Max) def buildMaxHeap(arr, n): for i in range(int(n / 2) - 1, -1, -1): MaxHeapify(arr, n, i) def mergeHeaps(merged, a, b, n, m): for i in range(n): merged[i] = a[i] for i in range(m): merged[n + i] = b[i] buildMaxHeap(merged, n + m) if __name__ == '__main__': a = [20, 15, 16, 12] b = [22, 17, 19] n = len(a) m = len(b) merged = [0] * (m + n) mergeHeaps(merged, a, b, n, m) for i in range(n + m): print(merged[i], end = " ")
Output: 22 20 19 12 15 17 16
Complexity
The time complexity for building a heap from an array of n elements is O(N). So, for the merging of two max-heaps, the time complexity will be O(N + M), where N will be the size of array1 and M will be the size of array2.
This article tried to discuss the concept to Merge two Binary Max-Heaps . Hope this blog helps you understand the concept. To practice problems on Heap you can check out MYCODE | Competitive Programming – Heaps.