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

Chia sẻ: Hấp Hấp | Ngày: | Loại File: PDF | Số trang:25

Thêm vào BST

Báo xấu

87
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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,

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

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 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 rr
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)