Implementation of Handwritten Heap (Max-Heap/Min-Heap)

Implementation of Handwritten Heap (Max-Heap/Min-Heap)

Problem Description
The implementation of a handwritten heap requires us to understand the core principles of the heap data structure and to be able to code its fundamental operations. A heap is a special kind of complete binary tree that satisfies the heap property: the value of each node is greater than or equal to (for a max-heap) or less than or equal to (for a min-heap) the values of its child nodes. Main operations include inserting an element (offer), removing the top element (poll), and inspecting the top element (peek).

Solution Process

1. Understanding the Heap's Storage Structure
A heap is usually stored using an array, leveraging the properties of a complete binary tree to quickly locate parent and child nodes.

For a node at index i in the array:
- Its parent index is (i - 1) / 2 (integer division).
- Its left child index is 2 * i + 1.
- Its right child index is 2 * i + 2.
Example: The left child of the root (index 0) is at index 1, and the right child is at index 2.

2. Defining the Basic Structure of the Heap Class
We'll use a min-heap as an example; the logic for a max-heap is similar (with the comparison direction reversed).

public class MinHeap {
    private int[] heap; // Array storing heap elements
    private int capacity; // Maximum capacity of the heap
    private int size; // Current number of elements in the heap

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

3. Implementing Core Helper Methods: heapifyUp and heapifyDown

heapifyUp (Sift Up): After inserting a new element at the bottom of the heap, the heap property might be violated. This method moves the element upwards until the property is restored.
1. Compare the current node's value with its parent's value.
2. If the current node's value is less than the parent's value (for a min-heap), swap them.
3. Repeat steps 1-2 until the current node is greater than or equal to its parent or reaches the root.
```
private void heapifyUp(int index) {
    while (index > 0) {
        int parentIndex = (index - 1) / 2;
        if (heap[index] >= heap[parentIndex]) break; // Heap property satisfied, exit
        swap(index, parentIndex); // Swap current node with parent
        index = parentIndex; // Continue checking upwards
    }
}
```

heapifyDown (Sift Down): After removing the top element, moving the bottom element to the top might violate the heap property. This method moves the element downwards.

Compare the current node with the smaller of its left and right children (for a min-heap).
If the current node's value is greater than this smaller value, swap them.
Repeat steps 1-2 until the current node is less than or equal to its children or has no children.

private void heapifyDown(int index) {
    while (index < size) {
        int leftChild = 2 * index + 1;
        int rightChild = 2 * index + 2;
        int smallest = index; // Assume current node is the smallest

        // Find the smallest among the current node, left child, and right child
        if (leftChild < size && heap[leftChild] < heap[smallest]) {
            smallest = leftChild;
        }
        if (rightChild < size && heap[rightChild] < heap[smallest]) {
            smallest = rightChild;
        }

        if (smallest == index) break; // Current node is already the smallest, stop sifting down
        swap(index, smallest);
        index = smallest; // Continue checking downwards
    }
}

4. Implementing Basic Operations

Insert Element (offer):

Place the new element at the end of the array (bottom of the heap).
Increment the heap size size.
Call heapifyUp on the last index to restore the heap property.

public void offer(int value) {
    if (size == capacity) throw new IllegalStateException("Heap is full");
    heap[size] = value; // Place at the end
    heapifyUp(size); // Sift up to adjust
    size++;
}

Remove Top Element (poll):

Save the top element (return value).
Move the bottom element to the top and decrement size.
Call heapifyDown on the top (index 0) to restore the heap property.

public int poll() {
    if (size == 0) throw new IllegalStateException("Heap is empty");
    int root = heap[0]; // Save the top element
    heap[0] = heap[size - 1]; // Move bottom element to the top
    size--;
    heapifyDown(0); // Sift down to adjust
    return root;
}

Inspect Top Element (peek):

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

5. Complete Code Example

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

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

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

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

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

    private void heapifyUp(int index) {
        while (index > 0) {
            int parent = (index - 1) / 2;
            if (heap[index] >= heap[parent]) break;
            swap(index, parent);
            index = parent;
        }
    }

    private void heapifyDown(int index) {
        while (index < size) {
            int left = 2 * index + 1;
            int right = 2 * index + 2;
            int smallest = index;
            if (left < size && heap[left] < heap[smallest]) smallest = left;
            if (right < size && heap[right] < heap[smallest]) smallest = right;
            if (smallest == index) break;
            swap(index, smallest);
            index = smallest;
        }
    }

    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
}

Key Points Summary

The heap is stored in an array, utilizing parent-child index relationships for efficient operations.
heapifyUp and heapifyDown are the core methods for maintaining the heap property, both with O(log n) time complexity.
Insertion and deletion operations have O(log n) time complexity, while inspecting the top is O(1).
In practice, heaps are commonly used in scenarios like priority queues and Top K problems.