Priority queue và binary heap: API và biểu diễn mảng

Giới thiệu

Bài này học hàng đợi ưu tiên qua lỗi phần mềm. Bạn lấy việc khẩn nhất trong $O(log n)$.

Kiến thức cần nhớ

Bài toán ưu tiên

• Nhiều việc, mỗi việc 1 độ khẩn khác nhau.
• Mỗi lần cần việc khẩn nhất, không cần xếp hết.
• Giữ list xếp sẵn thì chèn sửa rất đắt.
• Ví dụ đời thường: phòng cấp cứu khám ca nặng trước.

Hàng đợi ưu tiên và API

• Chỉ đảm bảo món lấy ra là khẩn nhất.
• Có chèn, lấy khẩn nhất, nhìn, đổi ưu tiên.
• Dùng như hộp đen, khỏi biết bên trong là gì.
• Ví dụ đời thường: bấm số thứ tự ưu tiên.

Min-heap, max-heap, mảng

• Max-heap đặt lớn nhất ở gốc.
• Min-heap đặt nhỏ nhất ở gốc.
• Cây hoàn chỉnh nhét vừa khít vào mảng.
• Ví dụ đời thường: sếp to nhất ngồi đỉnh tháp.
• Cha của i ở (i-1)//2, con ở 2i+1 và 2i+2.

Ví dụ

• Input: chèn lỗi ưu tiên 5, 9, 7 vào max-heap. Output: gốc là 9.
• Giải thích: cha luôn khẩn hơn con trên cùng đường.

💻 Bài tập

Ngôn ngữ: C++. Không dùng std::priority_queue, std::make_heap. Nộp vào day-023/.

Bài 1: Max-heap trên mảng

class MaxHeap {
 public:
  void push(int x);
  int  top() const;          // ném std::out_of_range nếu rỗng
  int  pop();                // lấy và trả gốc
  size_t size() const; bool empty() const;
  bool isValid() const;      // kiểm tra bất biến heap, dùng khi test
 private:
  std::vector<int> a;
  static size_t parent(size_t i) { return (i - 1) / 2; }
  static size_t left(size_t i)   { return 2 * i + 1; }
  static size_t right(size_t i)  { return 2 * i + 2; }
};

push 5, 9, 7          -> top = 9, mảng [9, 5, 7]
push 1, 12            -> top = 12
pop x5                -> 12, 9, 7, 5, 1
pop khi rỗng          -> ném out_of_range

Bài 2: Hàng đợi ưu tiên cho ticket hỗ trợ

struct Ticket { int priority; long long createdAt; std::string title; };

Viết TicketQueue dựa trên heap với comparator: ưu tiên cao hơn ra trước; cùng ưu tiên thì ticket tạo sớm hơn ra trước.

push (3, t=1, "A"), (5, t=2, "B"), (3, t=0, "C"), (5, t=3, "D")
pop hết -> B, D, C, A

Chuyển MaxHeap thành template Heap<T, Compare> để dùng chung.

Bài 3: So sánh 3 cách cài (nâng cao)

Cài hàng đợi ưu tiên bằng: (a) mảng chưa xếp, (b) mảng luôn xếp, (c) heap.

Chạy kịch bản $n = 10^5$: xen kẽ 2 lần push giá trị ngẫu nhiên và 1 lần pop. In bảng thời gian và độ phức tạp lý thuyết của từng thao tác.

impl         push     pop      tổng (ms)
unsorted     O(1)     O(n)     ...
sorted       O(n)     O(1)     ...
heap         O(logn)  O(logn)  ...

✅ Tiêu chí hoàn thành

• Test mẫu pass. Sau mỗi push/pop trong test ngẫu nhiên, isValid() là true.
• Kết quả pop hết khớp với sắp xếp giảm dần (test 1000 lần ngẫu nhiên).
• Bảng Bài 3 có số thật.
• Vẽ tay được cây và mảng tương ứng sau mỗi thao tác của test mẫu.

❓ Câu hỏi ôn tập

• Vì sao list xếp sẵn không đủ cho việc động?
• API hàng đợi ưu tiên có gì?
• Min-heap khác max-heap ở đâu?
• Công thức cha con trong mảng là gì?

🌕 Bạn đã hoàn thành ngày 23. Làm hết bài tập phía trên rồi sang ngày tiếp theo.