Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 13: Hàng đợi ưu tiên - Nguyễn Mạnh Hiển

Hàng đợi ưu tiên (priority queue) Nguyễn Mạnh Hiển Khoa Công nghệ thông tin hiennm@tlu.edu.vn Hàng đợi ưu tiên (priority queue) • Xóa phần tử nhỏ nhất (deleteMin) − Thời gian O(log N) • Chèn (insert) − Thời gian O(log N) Cài đặt hàng đợi ưu tiên • Danh sách liên kết − insert mất O(1) − deleteMin mất O(N) • Cây nhị phân tìm kiếm − insert và deleteMin mất O(log N) − Tuy nhiên, có tính chất không cần thiết: tất cả các phần tử được sắp xếp • Ta chỉ cần phần tử nhỏ nhất • Đống (heap) − Sự cài đặt phổ biến của hàng đợi ưu tiên − insert và deleteMin mất thời gian O(log N) Cây có thứ tự một phần • Cây có thứ tự một phần (partially ordered tree - POT) là cây T thỏa mãn: − Có quan hệ thứ tự “” xác định trên các nút của T − Đối với mỗi nút P và con C của nó: P  C • Suy ra: − Phần tử nhỏ nhất trong POT là gốc − Không có kết luận nào về thứ tự của các nút con Đống nhị phân (binary heap) • Đống nhị phân là một cây nhị phân đầy đủ có thứ tự một phần − Cây được lấp đầy trên tất cả các mức (level) trừ mức dưới cùng • Khi đề cập đến “đống”, ta hiểu rằng đó là “đống nhị phân” 0 3 2 4 5 gốc Biểu diễn vector của cây nhị phân đầy đủ • Lưu trữ các phần tử trong vector theo mức − Cha của v[k] = v[k/2] − Con trái của v[k] = v[2*k] − Con phải của v[k] = v[2*k + 1] R l r ll lr rr rl gốc rr rl lr ll r l R 7 6 5 4 3 2 1 Ví dụ về đống (heap) − Cha của v[k] = v[k/2] − Con trái của v[k] = v[2*k] − Con phải của v[k] = v[2*k + 1] Cây nào là đống? Cài đặt hàng đợi ưu tiên (đống) Ví dụ chèn: insert(14) 14 14 14 Thao tác đống cơ bản: insert(x) • Giữ tính chất cây nhị phân đầy đủ và sửa vấn đề cây có thứ tự một phần (partially ordered tree - POT) − Tạo nút lá (lỗ trống - hole) ứng với x ở tận cùng − Lặp lại: • Xác định nút cha của lỗ trống • Nếu POT không thỏa mãn: + Hoán đổi lỗ trống với nút cha • Ngược lại: + Dừng − Đặt x vào lỗ trống Cài đặt insert Ví dụ về deleteMin 31 13 14 16 19 21 19 68 65 26 32 31 Ví dụ về deleteMin (tiếp) 31 31 31 Thao tác đống cơ bản: deleteMin() • Xóa nút lá cuối cùng (đang chứa giá trị x); xóa giá trị của nút gốc  lỗ trống; gán x cho (nhưng chưa đặt vào) lỗ trống − Điều này đảm bảo tính chất cây nhị phân đầy đủ nhưng có thể vi phạm tính chất cây có thứ tự một phần (POT) • Lặp lại: − Xác định nút con nhỏ hơn của lỗ trống − Nếu POT không thỏa mãn: • Hoán đổi lỗ trống và nút con nhỏ hơn − Ngược lại: • Dừng • Đặt x vào lỗ trống Cài đặt deleteMin() Cài đặt deleteMin() (tiếp) Hàm tạo (constructor) • Xây dựng đống từ một tập các phần tử có thứ tự tùy ý • Các bước: − Chèn tất cả các phần tử vào cây mà không quan tâm tính chất cây có thứ tự một phần (POT) − Điều chỉnh cây để thỏa mãn POT, đi từ dưới lên • Thời gian chạy là O(N) (sẽ phân tích sau) Cài đặt hàm tạo Ví dụ percolateDown(7) percolateDown(6) percolateDown(5) percolateDown(1) percolateDown(4) percolateDown(3) percolateDown(2) Ví dụ (tiếp) Phân tích thời gian chạy của buildHeap() • Thời gian chạy  tổng chiều cao của tất cả các nút − Sẽ chứng minh tổng này = O(N) • Xét cây nhị phân hoàn hảo có chiều cao h: − Số nút: N = 2h+1 – 1 − Sẽ chứng minh tổng chiều cao các nút: S = 2h+1 – 1 – (h + 1) ( = O(N) ) Phân tích buildHeap() (tiếp) Nhân hai vế với 2: Lấy đẳng thức thứ hai trừ đẳng thức thứ nhất từng vế: Hàng đợi ưu tiên trong thư viện C++ • Lớp: priority_queue • Tệp tiêu đề: queue • Thực hiện theo kiểu đống cực đại (max-heap) thay vì đống cực tiểu (min-heap) như ta đang xét • Các phương thức chính: Ví dụ lập trình #include #include using namespace std; int main() { priority_queue pq; pq.push(4); pq.push(3); pq.push(5); cout << "Noi dung cua hang doi uu tien:" << endl; // Se in ra 5 4 3 while (!pq.empty()) { cout << pq.top() << endl; pq.pop(); } return 0; }