Heap Sort 🎯

Welcome to the world of data structures and algorithms! Today, we're diving into a fascinating sorting algorithm called Heap Sort. Let's get started!

What is Heap Sort? 📝

Heap Sort is an efficient sorting algorithm that takes advantage of Heap Data Structure. It's useful in sorting large data sets quickly.

Understanding Heap Data Structure 💡

A Heap is a binary tree where every parent node is greater than or equal to (Max Heap) or less than or equal to (Min Heap) its children. For a Max Heap, the root node always contains the maximum value.

Max Heap Example

In our case, we'll be using a Max Heap.

Building a Max Heap 🎯

To sort an array using Heap Sort, we first convert the given array into a Max Heap. Here's how to do it:

Start from the last non-leaf node (parent of the last child) and move upwards.
For each node, ensure it's larger than its children. If not, swap the node with the smaller child.
Repeat this process until the entire array is a Max Heap.

python

def build_max_heap(arr):
    n = len(arr)
    for i in range(n // 2, -1, -1):
        heapify(arr, n, i)

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2

    if l < n and arr[largest] < arr[l]:
        largest = l

    if r < n and arr[largest] < arr[r]:
        largest = r

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

Sorting the Array 🎯

Once the array is a Max Heap, we can sort it by following these steps:

Swap the first and last elements (root and last node).
Reduce the size of the heap by 1 (remove the last element).
Heapify the updated array from the new root node.
Repeat steps 1-3 until the entire array is sorted.

python

def heap_sort(arr):
    n = len(arr)
    build_max_heap(arr)

    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)

Real-World Application 💡

Heap Sort is useful in various real-world scenarios, such as sorting large datasets, job scheduling, and more. It's a powerful tool to have in your programming arsenal!

Practice Time 🎯

Now that you've learned about Heap Sort, let's put your knowledge to the test!