The Magic of Heaps: How They Power Your Favorite Algorithms

Day 13: Heaps: A Comprehensive Guide

Introduction to Heaps

Heaps are specialized binary trees that satisfy the heap property. In a max heap, the value of each node is greater than or equal to the values of its children. In a min heap, the value of each node is less than or equal to the values of its children.  

Applications of Heaps

• Priority Queues: Heaps are commonly used to implement priority queues, where elements are ordered based on their priority.
• Heap Sort: Heaps are used in the heap sort algorithm, a simple and efficient sorting algorithm.
• Graph Algorithms: Heaps are used in graph algorithms like Dijkstra’s algorithm for finding the shortest path between nodes.
• Data Structures: Heaps are used in data structures like Fibonacci heaps and binomial heaps.

Max Heap vs. Min Heap

Max Heap:

• The value of the parent node is always greater than or equal to the values of its children.
• Used in applications where the maximum value is required, such as priority queues for tasks with high priority.

Min Heap:

• The value of the parent node is always less than or equal to the values of its children.
• Used in applications where the minimum value is required, such as priority queues for tasks with low priority.

Heap Operations

• Insertion: Insert a new element at the end of the heap and then heapify up to maintain the heap property.
• Deletion: Remove the root element (maximum or minimum value) and replace it with the last element of the heap. Then, heapify down to maintain the heap property.
• Heapify: A process of rearranging the elements of a heap to satisfy the heap property.

Example: Heap Sort

Java

import java.util.Arrays;

class Heap {
    int[] arr;
    int n;

    public Heap(int cap) {
        arr = new int[cap];
        n = 0;
    }

    void insertKey(int k) {
        n++;
        arr[n - 1] = k;
        int i = n - 1;
        while (i != 0 && arr[i] > arr[(i - 1) / 2]) {
            int temp = arr[i];
            arr[i] = arr[(i - 1) / 2];
            arr[(i - 1) / 2] = temp;
            i = (i - 1) / 2;
        }
    }

    int extractMax() {
        if (n == 0) {
            return -1;
        }
        int max = arr[0];
        arr[0] = arr[n - 1];
        n--;
        heapify(0);
        return max;
    }

    void heapify(int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }

        if (right < n && arr[right]    > arr[largest]) {
            largest = right;
        }

        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            heapify(largest);
        }
    }

    void    buildMaxHeap() {
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(i);
        }
    }

    void heapSort() {
        buildMaxHeap();
        for (int i = n - 1; i >= 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(0);
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Heap h = new Heap(11);
        h.insertKey(10);
        h.insertKey(5);
        h.insertKey(20);
        h.insertKey(15);
        h.insertKey(8);

        System.out.println("Heap Sort:");
        h.heapSort();
        for (int i = 0; i < h.n; i++) {
            System.out.print(h.arr[i] + " ");
        }
    }
}

Use code with caution.

Conclusion

Heaps are versatile data structures with numerous applications in computer science. Understanding the concepts of max heaps, min heaps, and heap operations is essential for solving various problems efficiently. By mastering heaps, you can effectively implement priority queues, sorting algorithms, and other algorithms that require efficient handling of ordered elements.

Keywords: heaps, max heap, min heap, priority queue, heap sort, heapify, data structure, algorithm, computer science.

Also see: The Z Blogs

my other Blog: The Z Blog ZB