Heap Operations (Insert, Extract Min/Max) 🎯

Welcome to a deep dive into the fascinating world of Heaps! In this lesson, we'll explore the core operations of Heaps: Insert and Extract Min/Max, and learn how they can be used to solve real-world problems.

What is a Heap? 📝

A Heap is a specialized tree-based data structure that satisfies the Heap Property, which means the parent node is always greater than (Max Heap) or less than (Min Heap) its children. This property makes Heaps useful for solving a variety of optimization problems.

Why Heaps? 💡

Heaps are essential for solving problems that require frequent insertion and deletion of elements, finding the minimum or maximum element, or maintaining a priority queue. They are used in various algorithms like Dijkstra's Algorithm, Prim's Algorithm, and even in sorting algorithms like Heap Sort.

Heap Operations 📝

Insert

The Insert operation adds an element to the heap. The new element is placed at the bottom of the heap and then moved up (or down for Min Heap) to maintain the Heap Property.

python

def insert(heap, element):
    heap.append(element)
    swim(heap, len(heap) - 1)

def swim(heap, index):
    while index > 1 and heap[parent(index)][1] > heap[index][1]:
        heap[index], heap[parent(index)] = heap[parent(index)], heap[index]
        index = parent(index)

Note: heap is a list of tuples, where each tuple contains an element and its priority (in Min Heap, lower priority means higher priority).

Extract Min/Max

The Extract Min/Max operation removes the minimum/maximum element from the heap and maintains the Heap Property. The last element is replaced with the root, and then it's moved down (or up for Min Heap) to maintain the Heap Property.

python

def extract_min(heap):
    min_element = heap[1]
    last_element = heap.pop()

    if heap:
        last_element = heap[1]
        heap[1] = min_element
        sink(heap, 1)

    return min_element

def sink(heap, index):
    while True:
        left_child = 2 * index
        right_child = 2 * index + 1

        smallest = index

        if left_child <= len(heap) and heap[left_child][1] < heap[smallest][1]:
            smallest = left_child

        if right_child <= len(heap) and heap[right_child][1] < heap[smallest][1]:
            smallest = right_child

        if smallest == index:
            break

        heap[index], heap[smallest] = heap[smallest], heap[index]
        index = smallest

Note: parent(index) function returns the parent of a node with index index.

Practical Application 💡

Heaps are used in Dijkstra's Algorithm to find the shortest path in a graph. In this algorithm, a Min Heap is used to keep track of the shortest distance to each vertex.

Quiz 🎯

That's it for this lesson on Heap Operations! In the next lesson, we'll dive deeper into Heaps and explore more operations like Build Heap and Heapify. Stay tuned! 🚀