datastructures5MinHeap

1package pkg3datastructures;2 3/*4 * datastructures5MinHeap.java5 * ------------6 * A binary min-heap (array-based) supporting insert (sift-up) and7 * extractMin (sift-down). Foundation of priority queues and heap sort.8 *9 * COMPLEXITY: insert O(log n), extractMin O(log n), peek O(1), build O(n).10 * INDEXING: parent(i)=(i-1)/2, left(i)=2i+1, right(i)=2i+2.11 * WHEN TO USE: top-K, Dijkstra, scheduling, median maintenance.12 */13import java.util.*;14 15public class datastructures5MinHeap {16 17    private final List<Integer> heap = new ArrayList<>();18 19    void insert(int v) {20        heap.add(v);21        siftUp(heap.size() - 1);22    }23 24    int peek() {25        if (heap.isEmpty()) throw new NoSuchElementException("heap empty");26        return heap.get(0);27    }28 29    int extractMin() {30        if (heap.isEmpty()) throw new NoSuchElementException("heap empty");31        int min = heap.get(0);32        int last = heap.remove(heap.size() - 1);33        if (!heap.isEmpty()) { heap.set(0, last); siftDown(0); }34        return min;35    }36 37    int size() { return heap.size(); }38 39    private void siftUp(int i) {40        while (i > 0) {41            int parent = (i - 1) / 2;42            if (heap.get(i) >= heap.get(parent)) break;43            swap(i, parent);44            i = parent;45        }46    }47 48    private void siftDown(int i) {49        int n = heap.size();50        while (true) {51            int left = 2 * i + 1, right = 2 * i + 2, smallest = i;52            if (left < n && heap.get(left) < heap.get(smallest)) smallest = left;53            if (right < n && heap.get(right) < heap.get(smallest)) smallest = right;54            if (smallest == i) break;55            swap(i, smallest);56            i = smallest;57        }58    }59 60    private void swap(int a, int b) {61        int t = heap.get(a); heap.set(a, heap.get(b)); heap.set(b, t);62    }63 64    public static void main(String[] args) {65        datastructures5MinHeap h = new datastructures5MinHeap();66        int[] input = {5, 2, 8, 1, 9, 3, 7};67        for (int x : input) h.insert(x);68        System.out.println("min element: " + h.peek());69 70        StringBuilder sorted = new StringBuilder();71        while (h.size() > 0) sorted.append(h.extractMin()).append(' ');72        System.out.println("extracted ascending: " + sorted.toString().trim());73 74        // Built-in PriorityQueue for comparison (max-heap via comparator)75        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());76        for (int x : input) maxHeap.offer(x);77        System.out.println("max element (built-in): " + maxHeap.peek());78    }79}