Convert Max-Heap into Min-Heap using JavaScript
Given an array representing a max-heap, the problem is to convert this array into a min-heap using JavaScript.
Below are the approaches to convert the max-heap to min-heap using JavaScript:
Table of Content
- Naive Method
- In-Place Conversion
Naive Method
A common approach is to take the elements out of the max-heap, put them in an array, and use this array to construct the min-heap.
- Extract all elements from the max-heap.
- Use the array of extracted elements to build a new min-heap.
This approach is simple but not the most efficient, as it requires rebuilding the heap from the ground up.
Example: To demonstrate creating a max-heap to min-heap using naive approach 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 buildMaxHeap(arr) {
const n = arr.length;
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
maxHeapify(arr, n, i);
}
return arr;
}
function minHeapify(arr, n, i) {
let smallest = i;
let left = 2 * i + 1;
let right = 2 * i + 2;
if (left < n && arr[left] < arr[smallest]) {
smallest = left;
}
if (right < n && arr[right] < arr[smallest]) {
smallest = right;
}
if (smallest !== i) {
[arr[i], arr[smallest]] = [arr[smallest], arr[i]];
minHeapify(arr, n, smallest);
}
}
function buildMinHeap(arr) {
const n = arr.length;
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
minHeapify(arr, n, i);
}
return arr;
}
const numbers = [3, 1, 6, 5, 2, 4];
console.log("Original Array:", numbers);
const maxHeap = buildMaxHeap([...numbers]);
console.log("Max-Heap:", maxHeap);
const minHeap = buildMinHeap([...maxHeap]);
console.log("Converted Min-Heap from Max-Heap:", minHeap);
Output
Original Array: [ 3, 1, 6, 5, 2, 4 ] Max-Heap: [ 6, 5, 4, 1, 2, 3 ] Converted Min-Heap from Max-Heap: [ 1, 2, 3, 5, 6, 4 ]
Time Complexity: O(N)
Space Complexity: O(N)
In-Place Conversion
A higher-level approach is to modify the heap using the in-place conversion approach. Rearranging the current elements according to the min-heap property can be done without first obtaining them to a different structure.
- Iterate over the array representation of the max-heap from the last parent to the first.
- Apply the min-heapify procedure at each node.
Example: To demonstrate creating max-heap to min-heap using in-place conversion in JavaScript.
function minHeapify(arr, n, i) {
let smallest = i;
let left = 2 * i + 1;
let right = 2 * i + 2;
if (left < n && arr[left] < arr[smallest]) {
smallest = left;
}
if (right < n && arr[right] < arr[smallest]) {
smallest = right;
}
if (smallest !== i) {
[arr[i], arr[smallest]] = [arr[smallest], arr[i]];
minHeapify(arr, n, smallest);
}
}
function maxToMinHeap(arr) {
let n = arr.length;
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
minHeapify(arr, n, i);
}
return arr;
}
let maxHeap = [9, 5, 8, 3, 4];
console.log("Original Max-Heap:", maxHeap);
let minHeap = maxToMinHeap(maxHeap);
console.log("Converted Min-Heap:", minHeap);
Output
Original Max-Heap: [ 9, 5, 8, 3, 4 ] Converted Min-Heap: [ 3, 4, 8, 5, 9 ]
Time Complexity: O(N)
Space Complexity: O(logN)