Heap It Up: A Beginner’s Guide to Min-Heaps and Max-Heaps! - Part 2 : Sorting

Part 18 of data structures series. Let's code from scratch, our max heap!

Welcome back, young heapster! 👋 If you're here, it means that you've survived Part 1 of our Heap Sort adventure. You've conquered the mighty mountains 🗻 of Max Heaps and the mystical realms🏞 of Min Heaps. Now, it’s time to put those theory skills to work with some coding! 💻

PS: If you didn’t read the article about the theory behind Min & Max Heaps, check this article out!

🌟 Mission Objective

Implement the Heap Sort algorithm in JavaScript (just a personal choice, you can follow with me with any of your preferred programming languages), using your heap knowledge from Part 1. By the end, you’ll be able to sort an array in O(n log n) time complexity.

I will also try my best to make it a step-by-step tutorial, so you won’t get lost in the heap wilderness!

Ready? Ala Barakati Laah!!

---

🏗️ Problem Overview

Heap Sort is a sorting technique that sorts elements in an array. To make it efficient, it first converts the array into something called a Max Heap. And that’s what we’re going to do next!

Recap from Part1: What’s a Max Heap?

A Max Heap is a special kind of binary tree (think of a tree where each node has up to two children) that has a key rule:

• The largest value is at the top (the "root" of the tree).

• Each parent node is greater than or equal to its children.

Recap from Part1: Why Build a Max Heap for Sorting?

When the array is turned into a Max Heap, the biggest number is always at the top of the tree (root). This makes it easy to grab the biggest number, put it at the end of the array, and then reorganize the remaining part of the heap to repeat the process with the next largest value.

This way, we get the sorted elements one by one, from largest to smallest.

PS: I have written this article 3 repeated times, just to make it easy to grasp as possible! So just pay attention, and I’m sure you will nail it!

---

Step-by-Step Algorithm:

1. Build a Max Heap

1. Start with the array you want to sort, like [3, 1, 5, 7, 2, 4].

2. Rearrange the array to satisfy the Max Heap property (largest element at the root).

After building the Max Heap, it might look something like this if visualized as a tree:

        7
       / \
      5   4
     / \   \
    3   1   2

In array form, it’s [7, 5, 4, 3, 1, 2](that’s not a sorted array yet!).

2. Extract the Max Element and Sort

1. Take the root (7) and move it to the end of the array.

2. Reorganize the remaining elements to maintain the Max Heap structure.

3. Repeat this process until all elements are sorted.

---

Step-by-Step Example:

Input Array

Let's say we have this array to sort:

[3, 1, 6, 5, 2, 4]

Step 1: Build the Max Heap

We'll convert this array into a Max Heap by applying the heapify function from the bottom up. After building the Max Heap, the largest element will be at the root (first position of the array).

1. Initial Array: [3, 1, 6, 5, 2, 4]

2. Heapified Array (Max Heap): [6, 5, 4, 3, 2, 1]

This transformation arranges the array into a structure where every parent node is greater than or equal to its children, which is the Max Heap property.

Step 2: Extract the Largest Element to Sort

With the Max Heap in place, we can now repeatedly move the root (largest element) to the end of the array and "reduce" the heap size by one, applying heapify each time to maintain the Max Heap property in the reduced array.

1. Swap root with last element: [1, 5, 4, 3, 2, 6]

   • Heapify [1, 5, 4, 3, 2] → [5, 3, 4, 1, 2, 6]

2. Swap root with second-to-last element: [2, 3, 4, 1, 5, 6]

   • Heapify [2, 3, 4, 1] → [4, 3, 2, 1, 5, 6]

3. Swap root with third-to-last element: [1, 3, 2, 4, 5, 6]

   • Heapify [1, 3, 2] → [3, 1, 2, 4, 5, 6]

4. Swap root with fourth-to-last element: [2, 1, 3, 4, 5, 6]

   • Heapify [2, 1] → [2, 1, 3, 4, 5, 6]

5. Swap root with fifth-to-last element: [1, 2, 3, 4, 5, 6]

Final Output (Sorted Array)

After completing all the swaps and heapify steps, we end up with a sorted array:

[1, 2, 3, 4, 5, 6]

Summary of the Heap Sort Process on This Input

• Input: [3, 1, 6, 5, 2, 4]

• Max Heap: [6, 5, 4, 3, 2, 1]

• Sorted Output: [1, 2, 3, 4, 5, 6]

This sorted output shows how Max Heap Sort organizes the array in ascending order by converting it into a Max Heap and then repeatedly extracting the maximum elements.

---

How Do We Code from scratch a Max Heap?

The Heapify Process

To convert our array into a Max Heap, we use a process called heapify. Here’s how it works:

1. Start from the middle of the array (since elements at the end don’t have children) and check each element to make sure it follows the Max Heap rule.

2. For each element:

   • Check if it’s smaller than its children.

   • If it is, swap it with the larger child to make it the biggest in its little "family."

   • Keep doing this down the tree if necessary (called "sifting down").

---

👨‍💻Code Example Explained

I know you’re excited to code, so let’s start by implementing the heapify function (that will help us to convert an array to a max heap):

function heapify(arr, n, i) {
  let largest = i;         // Start by assuming the largest is the current node
  let left = 2 * i + 1;    // Left child index (based on array structure)
  let right = 2 * i + 2;   // Right child index

  // Check if left child is bigger than the current largest
  if (left < n && arr[left] > arr[largest]) {
    largest = left;        // If so, make left child the new "largest"
  }

  // Check if right child is bigger than the current largest
  if (right < n && arr[right] > arr[largest]) {
    largest = right;       // If so, make right child the new "largest"
  }

  // If the largest isn't the current node, swap and continue heapifying
  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]]; // Swap current node with largest
    heapify(arr, n, largest); // Recursively heapify the affected subtree
  }
}

Explanation of Each Part

1. Identify the Children: let left = 2 * i + 1; and let right = 2 * i + 2; calculate where the left and right children are in the array. These formulas come from the way heaps are stored in arrays.

2. Compare with Children:

   • First, check if the left child exists (left < n) and is bigger than the current node (arr[left] > arr[largest]).

   • Then, do the same with the right child.

   • Update largest to point to the biggest among the current node, left child, and right child.

3. Swap and Repeat (recursive call): If the biggest isn’t the current node, swap it with the biggest child. Then call heapify again on that child to keep the Max Heap property all the way down.

---

👨‍💻 Complete Heap Sort

Now that we understand heapify, here’s how Heap Sort works overall:

function heapSort(arr) {
  let n = arr.length;

  // Step 1: Build a max heap
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }

  // Step 2: One by one, extract elements from the heap
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];  // Move the root to the end
    heapify(arr, i, 0);                   // Heapify the reduced heap
  }
}

Explanation of Heap Sort Steps

1. Build the Max Heap: We start from the middle of the array (non-leaf nodes) and apply heapify to each one, working back up to the root. This ensures the entire array follows the Max Heap structure.

2. Extract Elements in Sorted Order:

   • Swap the root (largest element) with the last element in the heap.

   • "Reduce" the heap size by ignoring the last element (now in its final sorted position).

   • Heapify the root again to keep the Max Heap property.

   • Repeat this process until all elements are sorted.

---

And That’s Heap Sort! Congratulations🎉Heap Master!

By first creating a Max Heap, we can efficiently sort the array by repeatedly moving the largest element to its sorted position. Heap Sort takes O(n log n) time overall, making it a very efficient sorting algorithm for large datasets.

---

Final Challenge 🏆

As a bonus challenge, try creating a Min Heap Sort by adjusting heapify to maintain the Min Heap property (smallest elements on top). This will sort the array in descending order.

PS: I will not provide a solution for the Min Heap Sort, you should be able to do it yourself, and I’m sure you’re capable of doing it!

Gooood Luuuck Heapster 👋

🔔 Don't forget to subscribe to my blog and YouTube channel to stay updated with all the latest content!