Convert Min-Heap into Max-Heap using JavaScript
The objective is to create a max-heap from a given min-heap. To accomplish this, the elements of the array representing the min-heap must be rearranged such that the values of each parent node in the array are greater than or equal to those of its children.
Below are the approaches to achieve this which are as follows:
Table of Content
- Naive Method
- In-Place Conversion
Naive Method
The simplest approach is to create a new array by extracting the elements from the min-heap, and then use that array to create a max-heap.
- Extract elements from the min-heap to an array.
- Use this array to build a max-heap.
Example: To demonstrate converting a min-heap to a max-heap in JavaScript using the Naive method.
function maxHeapify(arr, i, n) {
let largest = i;
let left = 2 * i + 1;
let right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
maxHeapify(arr, largest, n);
}
}
function convertMinToMaxHeap(arr) {
let n = arr.length;
for (let i = Math
.floor(n / 2) - 1; i >= 0; i--) {
maxHeapify(arr, i, n);
}
return arr;
}
let minHeap = [1, 3, 5, 7, 9, 8, 10];
console.log("Original Min-Heap:", minHeap);
let maxHeap = convertMinToMaxHeap(minHeap);
console.log("Converted Max-Heap:", maxHeap);
Output
Original Min-Heap: [ 1, 3, 5, 7, 9, 8, 10 ] Converted Max-Heap: [ 10, 9, 8, 7, 3, 1, 5 ]
Time Complexity: O(N)
Space Complexity: O(N)
In-Place Conversion
In place conversion approach modifies the heap on the spot. Instead of extracting the elements into a different data structure, this approach rearranges them within the current heap structure to satisfy the max-heap property.
- Iterate over the array representation of the min-heap from the last parent node to the root.
- Apply a max-heapify process at each node.
Example: To demonsrtate converting a min heap to max heap using in-place conversion in JavaScript.
function maxHeapify(arr, n, i) {
let largest = i;
let left = 2 * i + 1;
let right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
maxHeapify(arr, n, largest);
}
}
function convertMinToMaxHeap(arr) {
let n = arr
.length;
for (let i = Math
.floor(n / 2) - 1; i >= 0; i--) {
maxHeapify(arr, n, i);
}
return arr;
}
let minHeap = [3, 5, 8, 17, 10, 9];
console.log("Original Min-Heap:", minHeap);
let maxHeap = convertMinToMaxHeap(minHeap);
console.log("Converted Max-Heap:", maxHeap);
Output
Original Min-Heap: [ 3, 5, 8, 17, 10, 9 ] Converted Max-Heap: [ 17, 10, 9, 5, 3, 8 ]
Time Complexity: O(N)
Space Complexity: (logN)