This article focuses on implementing a min-heap, which has the property that every parent node is less than or equal to its children. This ensures the smallest element is always at the root (index 1 in our array).

Heap Operations

A min-heap implementation should support these basic operations:

1. Insertion (I): Add a new element to the heap while maintaining the heap property
2. Peek minimum (PM): Retrieve the smallest element without removing it
3. Delete minimum (DM): Remove the smallest element and maintain the heap property
4. Delete by position (D): Remove an element at a specific position
5. Update (C): Modify an element at a specific position

Heap Maintenance Methods

The key to maintaining the heap property lies in two fundamental methods: siftUp and siftDown. These methods adjust the position of elements to ensure the heap property is preserved after insertions or deletions.

private static void siftDown(int nodeIndex) {
    int smallest = nodeIndex;
    int leftChild = 2 * nodeIndex;
    int rightChild = 2 * nodeIndex + 1;
    
    // Compare with left child
    if (leftChild <= heapSize && heapArray[leftChild] < heapArray[smallest]) {
        smallest = leftChild;
    }
    
    // Compare with right child
    if (rightChild <= heapSize && heapArray[rightChild] < heapArray[smallest]) {
        smallest = rightChild;
    }
    
    // If the smallest value is not the current node, swap and continue sifting
    if (smallest != nodeIndex) {
        int temp = heapArray[nodeIndex];
        heapArray[nodeIndex] = heapArray[smallest];
        heapArray[smallest] = temp;
        siftDown(smallest);
    }
}

private static void siftUp(int nodeIndex) {
    int parent = nodeIndex / 2;
    
    // If the current node is smaller than its parent, swap them
    if (parent > 0 && heapArray[nodeIndex] < heapArray[parent]) {
        int temp = heapArray[nodeIndex];
        heapArray[nodeIndex] = heapArray[parent];
        heapArray[parent] = temp;
        siftUp(parent);
    }
}

Core Operations Implementation

With these helper methods, implementing the heap operations becomes straightforward:

// Insert a new element into the heap
private static void insert(int value) {
    heapArray[++heapSize] = value;
    siftUp(heapSize);
}

// Retrieve the minimum element
private static int peekMin() {
    return heapArray[1];
}

// Remove and return the minimum element
private static int deleteMin() {
    int minValue = heapArray[1];
    heapArray[1] = heapArray[heapSize--];
    siftDown(1);
    return minValue;
}

// Remove an element at a specific position
private static void deleteAt(int position) {
    heapArray[position] = heapArray[heapSize--];
    siftDown(position);
    siftUp(position); // Ensures the element is in the correct position
}

// Update an element at a specific position
private static void update(int position, int newValue) {
    heapArray[position] = newValue;
    siftDown(position);
    siftUp(position); // Ensures the element is in the correct position
}

Complete Heap Implementation

Here's a complete implementation of a priority heap in Java with all the required operations:

import java.util.Scanner;

public class PriorityHeap {
    private static final int MAX_SIZE = 100010;
    private static int[] heapArray = new int[MAX_SIZE];
    private static int heapSize = 0;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int operations = scanner.nextInt();
        
        while (operations-- > 0) {
            String command = scanner.next();
            switch (command) {
                case "I":
                    int value = scanner.nextInt();
                    insert(value);
                    break;
                case "PM":
                    System.out.println(peekMin());
                    break;
                case "DM":
                    deleteMin();
                    break;
                case "D":
                    int position = scanner.nextInt();
                    deleteAt(position);
                    break;
                case "C":
                    int pos = scanner.nextInt();
                    int newVal = scanner.nextInt();
                    update(pos, newVal);
                    break;
            }
        }
        
        scanner.close();
    }

    private static void siftDown(int nodeIndex) {
        int smallest = nodeIndex;
        int leftChild = 2 * nodeIndex;
        int rightChild = 2 * nodeIndex + 1;
        
        if (leftChild <= heapSize && heapArray[leftChild] < heapArray[smallest]) {
            smallest = leftChild;
        }
        
        if (rightChild <= heapSize && heapArray[rightChild] < heapArray[smallest]) {
            smallest = rightChild;
        }
        
        if (smallest != nodeIndex) {
            int temp = heapArray[nodeIndex];
            heapArray[nodeIndex] = heapArray[smallest];
            heapArray[smallest] = temp;
            siftDown(smallest);
        }
    }

    private static void siftUp(int nodeIndex) {
        int parent = nodeIndex / 2;
        
        if (parent > 0 && heapArray[nodeIndex] < heapArray[parent]) {
            int temp = heapArray[nodeIndex];
            heapArray[nodeIndex] = heapArray[parent];
            heapArray[parent] = temp;
            siftUp(parent);
        }
    }

    private static void insert(int value) {
        heapArray[++heapSize] = value;
        siftUp(heapSize);
    }

    private static int peekMin() {
        return heapArray[1];
    }

    private static void deleteMin() {
        heapArray[1] = heapArray[heapSize--];
        siftDown(1);
    }

    private static void deleteAt(int position) {
        heapArray[position] = heapArray[heapSize--];
        siftDown(position);
        siftUp(position);
    }

    private static void update(int position, int newValue) {
        heapArray[position] = newValue;
        siftDown(position);
        siftUp(position);
    }
}