Heap và PriorityQueue

Queue phục vụ ai đến trước. Nhưng đơn gấp phải được đóng gói trước đơn thường, dù đến sau. Cần một hàng đợi luôn đưa ra phần tử ưu tiên nhất, và thêm vào vẫn nhanh. Đó là priority queue, bên trong là một heap.

Khái niệm

🏔️ Min-heap: cây nhị phân mà node cha luôn nhỏ hơn hoặc bằng hai con, nên phần tử nhỏ nhất luôn nằm ở gốc.

⏫ Priority queue (hàng đợi ưu tiên): hàng đợi mà poll luôn lấy phần tử có số ưu tiên (priority) nhỏ nhất, tức gấp nhất, không theo thứ tự đến.

Heap không cần xếp hết thứ tự như BST, chỉ cần cha không lớn hơn con. Cây được lấp đầy từng tầng, từ trái sang phải, nên lưu gọn trong một array: con của ô i nằm ở ô 2i + 1 và 2i + 2, cha nằm ở ô (i - 1) / 2.

Min-heap lưu trong array 2, 5, 4, 8

Thao tác	Big-O
Xem phần tử nhỏ nhất (`peek`)	O(1)
Thêm (`offer`)	O(log n)
Lấy phần tử nhỏ nhất (`poll`)	O(log n)

Ví dụ

Thêm vào heap: đặt ở cuối array, rồi đổi chỗ với cha chừng nào còn nhỏ hơn cha.

// Main.java
void main() {
    var heap = new MiniHeap();
    int[] values = {7, 3, 9, 1};
    for (int x : values) {
        heap.add(x);
        System.out.println(heap.getItems());
    }
}

// MiniHeap.java
import java.util.ArrayList;
import java.util.List;

class MiniHeap {
    private final List<Integer> items =
        new ArrayList<>();

    public List<Integer> getItems() {
        return items;
    }

    public void add(int value) {
        items.add(value);
        int i = items.size() - 1;
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (items.get(parent) <= items.get(i)) {
                break;
            }
            int temp = items.get(parent);
            items.set(parent, items.get(i));
            items.set(i, temp);
            i = parent;
        }
    }
}

Mỗi lần đổi chỗ đi lên một tầng. Cây có khoảng log n tầng, nên add là O(log n).
Lấy ra làm ngược lại: đưa phần tử cuối lên gốc, rồi đổi chỗ với con nhỏ hơn chừng nào còn lớn hơn con.
Ví dụ in ra [7], [3, 7], [3, 7, 9], [1, 3, 9, 7]. Số 1 thêm sau cùng đổi chỗ hai lần để lên gốc. Array không sắp xếp hẳn, nhưng gốc luôn nhỏ nhất.

Java có sẵn PriorityQueue<E>. Nó không nhận mức ưu tiên riêng mà so chính các phần tử với nhau, theo Comparator truyền vào constructor: offer thêm, poll() trả phần tử nhỏ nhất.

Thử ngay

Dùng PriorityQueue của Java cho ba đơn, mức 1 là gấp nhất. Mỗi đơn là một object Order gồm tên và mức ưu tiên:

// Main.java
void main() {
    var orders = new PriorityQueue<Order>(
        Comparator.comparingInt(o -> o.getPriority()));
    orders.offer(new Order("DH1 thường", 3));
    orders.offer(new Order("DH2 gấp", 1));
    orders.offer(new Order("DH3 vừa", 2));
    while (!orders.isEmpty()) {
        System.out.println(orders.poll().getName());
    }
}

// Order.java
class Order {
    private String name;
    private int priority;

    public Order(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }

    public String getName() { return name; }
    public int getPriority() { return priority; }
}

Đoán trước khi chạy: ba đơn ra theo thứ tự nào?

Xem kết quả

DH2 gấp
DH3 vừa
DH1 thường

poll luôn lấy mức nhỏ nhất, không quan tâm đơn nào vào trước. DH1 vào đầu tiên nhưng ra cuối cùng.

Lỗi hay gặp

Tưởng đơn cùng mức ưu tiên ra theo thứ tự đến. PriorityQueue không giữ thứ tự cho các phần tử cùng mức.

// SAI — DH1 đến trước nhưng DH3 có thể ra trước
var pq = new PriorityQueue<Order>(
    Comparator.comparingInt(o -> o.getPriority()));
pq.offer(new Order("DH1 thường", 2));
pq.offer(new Order("DH2 gấp", 1));
pq.offer(new Order("DH3 thường", 2));
// poll lần lượt: DH2 gấp, DH3 thường, DH1 thường

// ĐÚNG — mức ưu tiên kèm số thứ tự đến
var pq = new PriorityQueue<Order>(
    Comparator.comparingInt(o -> o.getPriority()));
pq.offer(new Order("DH1 thường", 2 * 1000 + 1));
pq.offer(new Order("DH2 gấp", 1 * 1000 + 2));
pq.offer(new Order("DH3 thường", 2 * 1000 + 3));
// poll lần lượt: DH2 gấp, DH1 thường, DH3 thường

Tóm tắt

Min-heap: cha nhỏ hơn hoặc bằng con, gốc là nhỏ nhất, lưu gọn trong array.
peek O(1), offer và poll O(log n).
PriorityQueue của Java lấy phần tử nhỏ nhất theo Comparator trước.
Cùng mức ưu tiên thì không giữ thứ tự đến. Cần thì ghép thêm số thứ tự.

Khái niệm

🏔️ Min-heap: cây nhị phân mà node cha luôn nhỏ hơn hoặc bằng hai con, nên phần tử nhỏ nhất luôn nằm ở gốc.

⏫ Priority queue (hàng đợi ưu tiên): hàng đợi mà poll luôn lấy phần tử có số ưu tiên (priority) nhỏ nhất, tức gấp nhất, không theo thứ tự đến.

Min-heap lưu trong array 2, 5, 4, 8

Thao tác	Big-O
Xem phần tử nhỏ nhất (`peek`)	O(1)
Thêm (`offer`)	O(log n)
Lấy phần tử nhỏ nhất (`poll`)	O(log n)

Ví dụ

Thêm vào heap: đặt ở cuối array, rồi đổi chỗ với cha chừng nào còn nhỏ hơn cha.

// Main.java
void main() {
    var heap = new MiniHeap();
    int[] values = {7, 3, 9, 1};
    for (int x : values) {
        heap.add(x);
        System.out.println(heap.getItems());
    }
}

// MiniHeap.java
import java.util.ArrayList;
import java.util.List;

class MiniHeap {
    private final List<Integer> items =
        new ArrayList<>();

    public List<Integer> getItems() {
        return items;
    }

    public void add(int value) {
        items.add(value);
        int i = items.size() - 1;
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (items.get(parent) <= items.get(i)) {
                break;
            }
            int temp = items.get(parent);
            items.set(parent, items.get(i));
            items.set(i, temp);
            i = parent;
        }
    }
}

Mỗi lần đổi chỗ đi lên một tầng. Cây có khoảng log n tầng, nên add là O(log n).
Lấy ra làm ngược lại: đưa phần tử cuối lên gốc, rồi đổi chỗ với con nhỏ hơn chừng nào còn lớn hơn con.
Ví dụ in ra [7], [3, 7], [3, 7, 9], [1, 3, 9, 7]. Số 1 thêm sau cùng đổi chỗ hai lần để lên gốc. Array không sắp xếp hẳn, nhưng gốc luôn nhỏ nhất.

Thử ngay

Dùng PriorityQueue của Java cho ba đơn, mức 1 là gấp nhất. Mỗi đơn là một object Order gồm tên và mức ưu tiên:

// Main.java
void main() {
    var orders = new PriorityQueue<Order>(
        Comparator.comparingInt(o -> o.getPriority()));
    orders.offer(new Order("DH1 thường", 3));
    orders.offer(new Order("DH2 gấp", 1));
    orders.offer(new Order("DH3 vừa", 2));
    while (!orders.isEmpty()) {
        System.out.println(orders.poll().getName());
    }
}

// Order.java
class Order {
    private String name;
    private int priority;

    public Order(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }

    public String getName() { return name; }
    public int getPriority() { return priority; }
}

Đoán trước khi chạy: ba đơn ra theo thứ tự nào?

Xem kết quả

DH2 gấp
DH3 vừa
DH1 thường

poll luôn lấy mức nhỏ nhất, không quan tâm đơn nào vào trước. DH1 vào đầu tiên nhưng ra cuối cùng.

Lỗi hay gặp

Tưởng đơn cùng mức ưu tiên ra theo thứ tự đến. PriorityQueue không giữ thứ tự cho các phần tử cùng mức.

// SAI — DH1 đến trước nhưng DH3 có thể ra trước
var pq = new PriorityQueue<Order>(
    Comparator.comparingInt(o -> o.getPriority()));
pq.offer(new Order("DH1 thường", 2));
pq.offer(new Order("DH2 gấp", 1));
pq.offer(new Order("DH3 thường", 2));
// poll lần lượt: DH2 gấp, DH3 thường, DH1 thường

// ĐÚNG — mức ưu tiên kèm số thứ tự đến
var pq = new PriorityQueue<Order>(
    Comparator.comparingInt(o -> o.getPriority()));
pq.offer(new Order("DH1 thường", 2 * 1000 + 1));
pq.offer(new Order("DH2 gấp", 1 * 1000 + 2));
pq.offer(new Order("DH3 thường", 2 * 1000 + 3));
// poll lần lượt: DH2 gấp, DH1 thường, DH3 thường

Tóm tắt

Min-heap: cha nhỏ hơn hoặc bằng con, gốc là nhỏ nhất, lưu gọn trong array.
peek O(1), offer và poll O(log n).
PriorityQueue của Java lấy phần tử nhỏ nhất theo Comparator trước.
Cùng mức ưu tiên thì không giữ thứ tự đến. Cần thì ghép thêm số thứ tự.

Khái niệm

Ví dụ

Thử ngay

Lỗi hay gặp

Tóm tắt

Tự kiểm tra

Heap và PriorityQueue

Khái niệm

Ví dụ

Thử ngay

Lỗi hay gặp

Tóm tắt

Tự kiểm tra