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

Bài giảng "Cấu trúc dữ liệu và giải thuật: Hàng đợi ưu tiên" cung cấp cho người đọc các kiến thức: Hàng đợi ưu tiên (priority queue), cài đặt hàng đợi ưu tiên, cây có thứ tự một phần, đây có thứ tự một phần, biểu diễn vector của cây nhị phân đầy đủ,... Mời các bạn cùng tham khảo nội dung chi tiết,
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Hàng đợi ưu tiên - Nguyễn Mạnh HiểnHàng đợi ưu tiên(priority queue)Nguyễn Mạnh HiểnKhoa Công nghệ thông tinhiennm@tlu.edu.vnHà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 gốc 0 3 2 4 5• Khi đề cập đến “đống”, ta hiểu rằng đó là “đống nhị phân”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] gốc R − Con phải của v[k] = v[2*k + 1] l r ll lr rl rr 1 2 3 4 5 6 7 R l r ll lr rl rrVí 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 14Thao 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ốngCài đặt insertVí dụ về deleteMin 31 13 14 16 19 21 19 68 65 26 32 31Ví dụ về deleteMin (tiếp) 31 31 31Thao 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ốngCà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ạoVí dụ percolateDown(7) percolateDown(6) percolateDown(5)