Max Heap ใน Java: ใช้งาน PriorityQueue แบบ descending

Max Heap คืออะไร?

Max Heap เป็น Binary Tree แบบสมบูรณ์ (Complete Binary Tree) ที่ค่าของแต่ละ parent node มีค่า >= ค่าของ child nodes ทั้งคู่ เริ่มจาก root node เป็นค่าสูงสุด

ตัวอย่าง: ใช้ PriorityQueue (Java Built-in)

import java.util.*; 

public class Demo { 
    public static void main(String args[]) { 
        // PriorityQueue ปกติเป็น Min Heap -> ใช้ reverseOrder() ทำให้เป็น Max Heap
        PriorityQueue maxHeap = new PriorityQueue<>(Collections.reverseOrder()); 
        
        maxHeap.add(43); 
        maxHeap.add(56); 
        maxHeap.add(99); 
        
        System.out.println("สมาชิกใน Priority Queue (Max Heap):"); 
        maxHeap.forEach(System.out::println); // 99, 43, 56 (ไม่เรียงเต็มที่ แค่ root มากที่สุด)
        
        maxHeap.poll(); // ลบค่าสูงสุด (root) ออก
        
        System.out.println("หลัง poll() - เหลือ:"); 
        maxHeap.forEach(System.out::println); // 56, 43
        
        Object[] arr = maxHeap.toArray(); 
        System.out.println("Array representation:"); 
        for (Object val : arr) 
            System.out.println("Value: " + val); 
    } 
}

ผลลัพธ์

สมาชิกใน Priority Queue (Max Heap): 
99 
43 
56 
หลัง poll() - เหลือ: 
56 
43 
Array representation: 
Value: 56 
Value: 43

คำอธิบาย

PriorityQueue ใน Java เป็น Min Heap โดยค่าเริ่มต้น ใช้ Collections.reverseOrder() หรือ Comparator.reverseOrder() เพื่อกลับลำดับเป็น Max Heap

ออปเตอร์ชันหลัก

การ Implement Max Heap เอง (ไม่ใช้ Library)

public class MaxHeap { 
    private int[] heap; 
    private int size; 
    
    public MaxHeap(int capacity) { 
        heap = new int[capacity]; 
        size = 0; 
    } 
    
    private int parent(int i) { return (i - 1) / 2; } 
    private int left(int i) { return 2 * i + 1; } 
    private int right(int i) { return 2 * i + 2; } 
    
    public void insert(int val) { 
        if (size == heap.length) throw new IllegalStateException("Heap full"); 
        heap[size] = val; 
        heapifyUp(size); 
        size++; 
    } 
    
    private void heapifyUp(int i) { 
        while (i > 0 && heap[i] > heap[parent(i)]) { 
            swap(i, parent(i)); 
            i = parent(i); 
        } 
    } 
    
    public int extractMax() { 
        if (size == 0) throw new IllegalStateException("Heap empty"); 
        int max = heap[0]; 
        heap[0] = heap[--size]; 
        heapifyDown(0); 
        return max; 
    } 
    
    private void heapifyDown(int i) { 
        int largest = i; 
        int l = left(i), r = right(i); 
        if (l < size && heap[l] > heap[largest]) largest = l; 
        if (r < size && heap[r] > heap[largest]) largest = r; 
        if (largest != i) { 
            swap(i, largest); 
            heapifyDown(largest); 
        } 
    } 
    
    private void swap(int i, int j) { 
        int tmp = heap[i]; heap[i] = heap[j]; heap[j] = tmp; 
    } 
}

การประยุกต์ใช้

• Priority Scheduling (OS, Job Queue)
• Dijkstra / A* Algorithm (priority queue)
• Top-K problems (หา K ค่าสูงสุด)
• Heap Sort

Memory Leak ใน Java: สาเหตุ ตัวอย่าง และการป้องกัน

JVM Stack Area: โครงสร้าง การทำงาน และคุณสมบัติ