educative.io

Question about Min Heap

Courses
,
#1

Why is the heap setup for loop using let i = Math.floor(n / 2) - 1; are the initial value. Its appears to be an optimized solution. Using let n = 0; provides the same solution, just dont understand the significance of this initial value

function maxHeapify(arr, n, i) {
let max = i;
const left = 2 * i + 1;
const right = 2 * i + 2;

if (left < n && arr[max] < arr[left]) {
max = left;
}

if (right < n && arr[max] < arr[right]) {
max = right;
}

if (max !== i) {
[arr[i], arr[max]] = [arr[max], arr[i]]
maxHeapify(arr, n, max)
}
}

function makeHeap(arr) {
let n = arr.length;
// Build max heap
for (let i = Math.floor(n / 2) - 1; i >= 0; i–) {
maxHeapify(arr, n, i);
}
// Perform heap sort
for (let i = n - 1; i > 0; i–) {
[arr[i], arr[0]] = [arr[0], arr[i]]; // swap root with the last element
n–;
maxHeapify(arr, i, 0); // Heapify root element
}
return arr;
}

Also how would the code vary to work with a min heap instead or max heap?

Thanks in advanced!

Course: Educative: Interactive Courses for Software Developers
Lesson: Heap Sort (Implementation) - Mastering Data Structures and Sorting Algorithms in JavaScript

#2

The initial value Math.floor(n / 2) - 1 in the heap setup loop of the makeHeap function is strategically chosen to optimize the process of building the heap efficiently. This value ensures that the loop starts from the parent nodes of the last level of the heap, progressing upwards towards the root. By focusing on nodes that are likely to have children, unnecessary iterations over leaf nodes are avoided, resulting in improved performance during heap construction.

As for adapting the code for min heaps, modifications need to be made to the maxHeapify function to prioritize smaller elements and maintain the min heap property. Additionally, the makeHeap function should be updated to call the modified minHeapify function appropriately to construct the min heap. I’ve provided a modified version of the code below to work with min heaps:

function minHeapify(arr, n, i) {
    let min = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;

    if (left < n && arr[min] > arr[left]) {
        min = left;
    }

    if (right < n && arr[min] > arr[right]) {
        min = right;
    }

    if (min !== i) {
        [arr[i], arr[min]] = [arr[min], arr[i]];
        minHeapify(arr, n, min);
    }
}

function makeHeap(arr) {
    let n = arr.length;
    // Build min heap
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        minHeapify(arr, n, i);
    }
    // Perform heap sort
    for (let i = n - 1; i > 0; i--) {
        [arr[i], arr[0]] = [arr[0], arr[i]]; // swap root with the last element
        n--;
        minHeapify(arr, i, 0); // Heapify root element
    }
    return arr;
}
#3

Thanks Komal! Appreciate the quick response