Heap

title: Heap (DSA) description: Min-heap aur Max-heap implementation

Complete binary tree. Min-heap: parent ≤ children. Max-heap: parent ≥ children.

Min-Heap using Array

class MinHeap { private int[] heap; private int size; MinHeap(int capacity) { heap = new int[capacity]; size = 0; } int parent(int i) { return (i - 1) / 2; } int left(int i) { return 2 * i + 1; } int right(int i) { return 2 * i + 2; } void insert(int val) { heap[size++] = val; // Bubble up int i = size - 1; while (i > 0 && heap[parent(i)] > heap[i]) { swap(i, parent(i)); i = parent(i); } } int extractMin() { int min = heap[0]; heap[0] = heap[--size]; heapifyDown(0); return min; } void heapifyDown(int i) { int smallest = i, l = left(i), r = right(i); if (l < size && heap[l] < heap[smallest]) smallest = l; if (r < size && heap[r] < heap[smallest]) smallest = r; if (smallest != i) { swap(i, smallest); heapifyDown(smallest); } } void swap(int i, int j) { int t = heap[i]; heap[i] = heap[j]; heap[j] = t; } int peek() { return heap[0]; } boolean isEmpty() { return size == 0; } }

Java PriorityQueue (Built-in Heap)

java exampleWoHoTech

// Min-Heap
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// Max-Heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

// Top K elements
int[] topK(int[] arr, int k) {
    PriorityQueue<Integer> minH = new PriorityQueue<>();
    for (int n : arr) {
        minH.offer(n);
        if (minH.size() > k) minH.poll(); // Remove smallest
    }
    return minH.stream().mapToInt(Integer::intValue).toArray();
}

// Kth largest
int kthLargest(int[] arr, int k) {
    PriorityQueue<Integer> minH = new PriorityQueue<>();
    for (int n : arr) {
        minH.offer(n);
        if (minH.size() > k) minH.poll();
    }
    return minH.peek();
}

title: Heap (DSA) description: Min-heap aur Max-heap implementation

Complete binary tree. Min-heap: parent ≤ children. Max-heap: parent ≥ children.

Min-Heap using Array

Java PriorityQueue (Built-in Heap)

java exampleWoHoTech

// Min-Heap
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// Max-Heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

// Top K elements
int[] topK(int[] arr, int k) {
    PriorityQueue<Integer> minH = new PriorityQueue<>();
    for (int n : arr) {
        minH.offer(n);
        if (minH.size() > k) minH.poll(); // Remove smallest
    }
    return minH.stream().mapToInt(Integer::intValue).toArray();
}

// Kth largest
int kthLargest(int[] arr, int k) {
    PriorityQueue<Integer> minH = new PriorityQueue<>();
    for (int n : arr) {
        minH.offer(n);
        if (minH.size() > k) minH.poll();
    }
    return minH.peek();
}

Min-Heap using Array

Java PriorityQueue (Built-in Heap)

Continue learning this concept

Heap

Min-Heap using Array

Java PriorityQueue (Built-in Heap)

Continue learning this concept