🧠 Today I Studied Heap Sort and Solved Heap-Based Tasks in Python

🚀 What I Did Today

After learning about heaps (max heap, min heap, and their operations), I decided to take it further. I implemented:

• A full Heap Sort using a max heap

• A custom solution to find the k largest elements in an array using a min-heap via heapq

Here’s how both went 👇

---

🏗️ Implementing Heap Sort (Using Max Heap)

array = [4, 1, 2, 7, 9]

def heapfy_max(array, n, i):
    largest = i
    left = 2*i + 1
    right = 2*i + 2

    if left < n and array[left] > array[largest]:
        largest = left

    if right < n and array[right] > array[largest]:
        largest = right

    if largest != i:
        array[i], array[largest] = array[largest], array[i]
        heapfy_max(array, n, largest)

n = len(array)

# Step 1: Build max heap
for i in range(n // 2 - 1, -1, -1):
    heapfy_max(array, n, i)

# Step 2: Extract elements from the heap
for i in range(n - 1, 0, -1):
    array[0], array[i] = array[i], array[0]  # Move max to the end
    heapfy_max(array, i, 0)  # Heapify the reduced heap

print(array)

✅ Output:

[1, 2, 4, 7, 9]

This is a great in-place sorting algorithm with time complexity O(n log n).

---

🎯 Task: Find the K Largest Elements in an Array

The goal here was to find the top 3 largest elements from an unsorted array using a min-heap. This keeps memory usage small and is efficient.

📌 Python Code:

import heapq

array = [10, 40, 80, 4, 7, 90, 45, 79, 50]
k = 3
min_heap = []

for element in array:
    if len(min_heap) < k:
        heapq.heappush(min_heap, element)
    else:
        if element > min_heap[0]:
            heapq.heappop(min_heap)
            heapq.heappush(min_heap, element)

sorted_result = sorted(min_heap, reverse=True)
print(sorted_result)

✅ Output:

[90, 80, 79]

---

🧠 What I Learned

• Heap Sort uses a max heap to sort elements in ascending order.

• Python’s heapq is a powerful tool for tasks like "k largest elements."

• Min-heaps are useful for keeping track of smallest/largest items efficiently.

• Heap-based solutions scale well and are great for large datasets.