DSA: Heap

A heap is a specialized tree-based data structure that satisfies the heap property. It is commonly used to implement priority queues and efficient sorting algorithms like heap sort. Heaps are usually implemented as binary heaps, which means each node has at most two children.

There are two types of heaps: max heap and min heap.

Max Heap

In a max heap, the value of each node is greater than or equal to the values of its children.
The root node contains the maximum value in the heap.
The maximum value can be efficiently retrieved in constant time (O(1)) by accessing the root node.
The maximum value can be removed in logarithmic time (O(log n)) by removing the root node and reorganizing the heap.

Min Heap:

In a min heap, the value of each node is smaller than or equal to the values of its children.
The root node contains the minimum value in the heap.
The minimum value can be efficiently retrieved in constant time (O(1)) by accessing the root node.
The minimum value can be removed in logarithmic time (O(log n)) by removing the root node and reorganizing the heap.

Heap Operations:

Peek: Retrieves the maximum value in a max heap or the minimum value in a min-heap without removing it. This operation has a time complexity of O(1).
Poll: Retrieves and removes the maximum value in a max heap or the minimum value in a min-heap. After removal, the heap is reorganized to maintain the heap property. This operation has a time complexity of O(log n).
Add: Inserts a new element into the heap while maintaining the heap property. The new element is placed at the next available position and then “bubbled up” or “bubbled down” to its correct position. This operation has a time complexity of O(log n).
isEmpty: Checks if the heap is empty. This operation has a time complexity of O(1).
Size: Returns the number of elements currently stored in the heap. This operation has a time complexity of O(1).

Heap Implementation:

Heaps are commonly implemented using arrays. The binary tree structure is represented implicitly in the array, where each node is stored at a specific index. The left child of a node at index i can be found at index (2 * i) + 1, and the right child can be found at index (2 * i) + 2. The parent of a node at index i can be found at index (i – 1) / 2.

When adding elements to a heap, the new element is inserted at the next available position and then “bubbled up” by repeatedly swapping it with its parent until the heap property is satisfied.

When removing elements from a heap, the root node is removed and replaced with the last element in the heap. Then, the new root node is “bubbled down” by comparing it with its children and swapping with the smaller child (in the case of a min-heap) or the larger child (in the case of a max heap) until the heap property is satisfied.

Heaps are efficient data structures for maintaining a partially ordered set and performing operations such as finding the maximum/minimum element or efficiently sorting elements. They are widely used in various algorithms and applications where efficient priority queue operations are required.

Code example of a min heap implementation in Java:

import java.util.Arrays;

public class MinHeap {
    private int[] heap;
    private int size;
    private int capacity;

    public MinHeap(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.heap = new int[capacity];
    }

    private int getParentIndex(int index) {
        return (index - 1) / 2;
    }

    private int getLeftChildIndex(int index) {
        return (2 * index) + 1;
    }

    private int getRightChildIndex(int index) {
        return (2 * index) + 2;
    }

    private boolean hasParent(int index) {
        return getParentIndex(index) >= 0;
    }

    private boolean hasLeftChild(int index) {
        return getLeftChildIndex(index) < size;
    }

    private boolean hasRightChild(int index) {
        return getRightChildIndex(index) < size;
    }

    private void swap(int index1, int index2) {
        int temp = heap[index1];
        heap[index1] = heap[index2];
        heap[index2] = temp;
    }

    private void heapifyUp() {
        int index = size - 1;
        while (hasParent(index) && heap[index] < heap[getParentIndex(index)]) {
            swap(index, getParentIndex(index));
            index = getParentIndex(index);
        }
    }

    private void heapifyDown() {
        int index = 0;
        while (hasLeftChild(index)) {
            int smallerChildIndex = getLeftChildIndex(index);
            if (hasRightChild(index) && heap[getRightChildIndex(index)] < heap[smallerChildIndex]) {
                smallerChildIndex = getRightChildIndex(index);
            }

            if (heap[index] < heap[smallerChildIndex]) {
                break;
            } else {
                swap(index, smallerChildIndex);
            }

            index = smallerChildIndex;
        }
    }

    public int peek() {
        if (size == 0) {
            throw new IllegalStateException("Heap is empty.");
        }
        return heap[0];
    }

    public int poll() {
        if (size == 0) {
            throw new IllegalStateException("Heap is empty.");
        }
        int item = heap[0];
        heap[0] = heap[size - 1];
        size--;
        heapifyDown();
        return item;
    }

    public void add(int item) {
        if (size == capacity) {
            throw new IllegalStateException("Heap is full.");
        }
        heap[size] = item;
        size++;
        heapifyUp();
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    @Override
    public String toString() {
        return Arrays.toString(Arrays.copyOfRange(heap, 0, size));
    }

    public static void main(String[] args) {
        MinHeap minHeap = new MinHeap(10);
        minHeap.add(4);
        minHeap.add(2);
        minHeap.add(7);
        minHeap.add(1);
        minHeap.add(5);

        System.out.println("Heap: " + minHeap);  // Output: Heap: [1, 2, 7, 4, 5]
        System.out.println("Peek: " + minHeap.peek());  // Output: Peek: 1

        int item = minHeap.poll();
        System.out.println("Popped item: " + item);  // Output: Popped item: 1
        System.out.println("Heap after poll: " + minHeap);  // Output: Heap after poll: [2, 4, 7, 5]

        minHeap.add(0);
        System.out.println("Heap after adding 0: " + minHeap);  // Output: Heap after adding 0: [0, 2, 7, 5, 4]
    }
}

In this example, we create a MinHeap class with the necessary methods to implement a min-heap. We use an array to store the heap elements, and the size and capacity variables to keep track of the heap size.

The methods getParentIndex, getLeftChildIndex, and getRightChildIndex are helper methods to calculate the indices of parent and child nodes based on the current index.

The methods hasParent, hasLeftChild, and hasRightChild check if a node has a parent or children.

The swap method is used to swap two elements in the heap array.

The heapifyUp method is called after adding a new element to the heap to restore the heap property by bubbling up the element until it reaches its correct position.

The heapifyDown method is called after removing the root element to restore the heap property by bubbling down the new root until it reaches its correct position.

The peek method returns the minimum value in the heap without removing it.

The poll method returns and removes the minimum value from the heap.

The add method adds a new element to the heap while maintaining the heap property.

The isEmpty method checks if the heap is empty.

The size method returns the current size of the heap.

The toString method is overridden to provide a string representation of the heap elements.

In the main method, we create a MinHeap object, add elements, and perform operations like peek and poll to demonstrate the functionality of the min heap implementation.

The time and space complexity of a heap data structure is as follows:

Time Complexity:

Peek: O(1) – Since the maximum or minimum value is always at the root, retrieving it takes constant time.
Poll: O(log n) – Removing the maximum or minimum value and reorganizing the heap requires traversing the tree from the root to the leaf level, which takes logarithmic time.
Add: O(log n) – Adding a new element to the heap and reorganizing the heap to maintain the heap property also requires traversing the tree, which takes logarithmic time.
isEmpty: O(1) – Checking if the heap is empty can be done in constant time.
Size: O(1) – Returning the number of elements in the heap can be done in constant time.

Space Complexity:

The space complexity of a heap data structure is O(n), where n is the number of elements stored in the heap. This accounts for the array used to store the elements.

Overall, heaps provide efficient operations for maintaining a partially ordered set and performing priority queue operations. The logarithmic time complexity for the poll and add operations makes heaps suitable for scenarios where efficient retrieval of the maximum or minimum element is required.

I hope this explanation provides a comprehensive understanding of the heap data structure in data structures and algorithms.

Note: also read about DSA: Tries