12. Heaps (Đống)

🎯 Mục tiêu học tập

• Hiểu cấu trúc heap và heap property
• Cài đặt min heap và max heap
• Thuật toán heapify và heap sort
• Ứng dụng heap vào priority queue

📚 Lý thuyết

Heap là gì?

Định nghĩa: Complete binary tree thỏa mãn heap property.

Heap Property:

• Max Heap: Parent ≥ Children (root là max)
• Min Heap: Parent ≤ Children (root là min)

Đặc điểm:

• Complete binary tree (fill từ trái sang phải)
• Height = O(log n)
• Thường implement bằng array

🏗️ Array Representation

// Với node ở index i:
// Left child: 2*i + 1
// Right child: 2*i + 2  
// Parent: (i-1)/2

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

🔧 Basic Operations

1. Insert (O(log n))

void insert(int value) {
    // 1. Thêm vào cuối array
    heap[size] = value;
    size++;

    // 2. Heapify up
    heapifyUp(size - 1);
}

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

2. Extract Min/Max (O(log n))

int extractMin() {
    // 1. Lưu root
    int min = heap[0];

    // 2. Move last element to root
    heap[0] = heap[size - 1];
    size--;

    // 3. Heapify down
    heapifyDown(0);
    return min;
}

void heapifyDown(int index) {
    while (true) {
        int smallest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;

        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;
    }
}

3. Peek (O(1))

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

4. Build Heap (O(n))

void buildHeap(int[] array) {
    heap = Arrays.copyOf(array, array.length);
    size = array.length;

    // Heapify từ last internal node về root
    for (int i = (size - 2) / 2; i >= 0; i--) {
        heapifyDown(i);
    }
}

🎯 Applications

1. Priority Queue

PriorityQueue<Integer> pq = new PriorityQueue<>();  // Min heap
PriorityQueue<Integer> maxPq = new PriorityQueue<>(Collections.reverseOrder());

2. Heap Sort

void heapSort(int[] arr) {
    // 1. Build max heap
    buildMaxHeap(arr);

    // 2. Extract max repeatedly
    for (int i = arr.length - 1; i > 0; i--) {
        swap(0, i);  // Move max to end
        heapifyDown(0, i);  // Heapify reduced heap
    }
}

3. K-way Merge

// Merge k sorted arrays
PriorityQueue<Element> pq = new PriorityQueue<>();
// Add first element from each array
// Keep extracting min and adding next element

4. Top K Problems

// Find K largest elements
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
    minHeap.offer(num);
    if (minHeap.size() > k) {
        minHeap.poll();
    }
}

🔍 Types of Heaps

1. Binary Heap

• Standard heap với 2 children per node
• Array implementation

2. d-ary Heap

• d children per node
• Reduce height nhưng increase heapify cost

3. Fibonacci Heap

• Advanced heap với better amortized complexity
• Decrease key: O(1) amortized

4. Binomial Heap

• Forest of binomial trees
• Union operation: O(log n)

📊 Complexity Analysis

Operation	Binary Heap	Fibonacci Heap
Insert	O(log n)	O(1) amortized
Extract Min	O(log n)	O(log n) amortized
Decrease Key	O(log n)	O(1) amortized
Union	O(n)	O(1)
Find Min	O(1)	O(1)

📋 Bài tập thực hành

Cơ bản:

1. Implement min heap và max heap
2. Heap sort implementation
3. Kth largest element in array
4. Merge k sorted lists

Trung bình:

1. Top K frequent elements
2. Find median from data stream
3. Ugly Number II
4. Meeting Rooms II

Nâng cao:

1. Sliding window median
2. Smallest range covering K lists
3. IPO problem
4. Minimum cost to hire K workers

💡 Optimization Tips

1. Space Optimization

// In-place heap sort
// Use existing array as heap

2. Custom Comparators

PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);

3. Lazy Deletion

// Mark as deleted instead of actually removing
// Clean up during next operation

⚠️ Common Mistakes

1. Index Calculation

// Wrong: parent = i/2 (for 1-indexed)
// Right: parent = (i-1)/2 (for 0-indexed)

2. Build Heap

// Inefficient: Insert one by one O(n log n)
// Efficient: Bottom-up heapify O(n)

3. Heap vs Priority Queue

// Java PriorityQueue là min heap by default
// Muốn max heap: PriorityQueue<>(Collections.reverseOrder())

🚀 Chuẩn bị code

mkdir 12-heaps
# Files:
# - MinHeap.java
# - MaxHeap.java  
# - HeapSort.java
# - PriorityQueueApplications.java
# - HeapProblems.java