Data Structures and Algorithms: Implementing Heaps 🎯

Welcome to the exciting world of Data Structures and Algorithms! In this lesson, we'll dive deep into Heaps – a fundamental data structure that will help you solve complex problems efficiently. Let's get started!

Introduction to Heaps 📝

A heap is a specialized tree-based data structure that satisfies the heap property. It is used for efficient sorting and priority queue operations. There are two types of heaps: Max Heap and Min Heap.

Max Heap and Min Heap 💡

Max Heap: In a Max Heap, the root node always stores the maximum value. The left child of any node has a value greater than or equal to the parent node.
Min Heap: In a Min Heap, the root node always stores the minimum value. The left child of any node has a value less than or equal to the parent node.

Building a Heap from an Array 📝

To create a heap, we need to follow the Heapify algorithm. This algorithm builds a heap from an arbitrary array.

Here's the step-by-step process:

Start from the last parent node (index parent = (length - 1) / 2).
Compare the parent node with its left and right children.
If the parent node is smaller than either child, swap the parent and larger child.
Recursively apply this process to the swapped child node.
Repeat until the entire array is a heap.

Implementing Heap Operations 📝

Now that we have a heap, let's implement some essential operations:

Insert: Add a new element to the heap by appending it to the end and then heapify the array.
Delete Max (Min): Remove the root node and replace it with the last node. Then, restore the heap property by heapify the root node.
Extract Max (Min): Remove the root node and return it.
Decrease Key: Update the key of an existing node, then heapify the affected node and its ancestors.

Code Examples ✅

Max Heap Implementation (Python)

python

class MaxHeap:
    def __init__(self, arr=None):
        if arr:
            self.heapify(arr)
        self.heap = []

    def heapify(self, arr):
        for i in range(len(arr) // 2, -1, -1):
            self._heapify(arr, i, len(arr))

    def _heapify(self, arr, i, length):
        largest = i
        l = 2 * i + 1
        r = 2 * i + 2

        if l < length and arr[l] > arr[largest]:
            largest = l

        if r < length and arr[r] > arr[largest]:
            largest = r

        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
            self._heapify(arr, largest, length)

    def insert(self, value):
        self.heap.append(value)
        self.heapify(self.heap)

    def delete_max(self):
        if len(self.heap) == 0:
            return None

        max_val = self.heap[0]
        self.heap[0] = self.heap[-1]
        self.heap.pop()
        self._heapify(self.heap, 0, len(self.heap))
        return max_val

    def extract_max(self):
        if len(self.heap) == 0:
            return None

        max_val = self.heap[-1]
        self.heap.pop()
        if self.heap:
            self.heap[-1] = self.heap[0]
            self.heap[0] = None
            self._heapify(self.heap, 0, len(self.heap))
        return max_val

    def decrease_key(self, index, key):
        if index >= len(self.heap) or key < self.heap[index]:
            return

        self.heap[index] = key
        self._heapify(self.heap, index, len(self.heap))

### Min Heap Implementation (Python)

```python
class MinHeap:
    def __init__(self, arr=None):
        if arr:
            self.heapify(arr)
        self.heap = []

    def heapify(self, arr):
        for i in range(len(arr) // 2, -1, -1):
            self._heapify(arr, i, len(arr))

    def _heapify(self, arr, i, length):
        smallest = i
        l = 2 * i + 1
        r = 2 * i + 2

        if l < length and arr[l] < arr[smallest]:
            smallest = l

        if r < length and arr[r] < arr[smallest]:
            smallest = r

        if smallest != i:
            arr[i], arr[smallest] = arr[smallest], arr[i]
            self._heapify(arr, smallest, length)

    # Rest of the methods (insert, delete_min, extract_min, decrease_key) are similar to the MaxHeap implementation

Quiz 🎯

That's it for this lesson on Heaps! In the next lesson, we'll dive deeper into common heap operations and explore real-world applications. Stay tuned! 🎉