›

Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 11: Hàng ưu tiên - Hoàng Thị Điệp

pdf 45 trang huongle 3470
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 11: Hàng ưu tiên - Hoàng Thị Điệp", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_cau_truc_du_lieu_va_giai_thuat_bai_11_hang_uu_tien.pdf

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 11: Hàng ưu tiên - Hoàng Thị Điệp

  1. Bài 11: Hàng ưu tiên Giảng viên: Hoàng Thị Điệp Khoa Công nghệ Thông tin – Đại học Công Nghệ Cấu trúc dữ liệu và giải thuật HKI, 2013-2014
  2. Nội dung chính 1. KDLTT hàng ưu tiên 2. Các phương pháp cài đặt 3. Ứng dụng: xây dựng mã Huffman 2 diepht@vnu
  3. KDLTT hàng ưu tiên (priority queue)  Là tập hợp trong đó mỗi  removeMin() loại bỏ và trả phần tử là một cặp (giá trị về đối tượng có giá trị ưu ưu tiên, đối tượng) tiên nhỏ nhất. Thực hiện được nếu hàng không rỗng.  ta có thể so sánh được các giá trị ưu tiên  findMinKey() tìm giá trị ưu tiên nhỏ nhất .Thực hiện  Các phép toán được nếu hàng không rỗng  insert(k, o) xen vào hàng  size() ưu tiên đối tượng o có giá  isEmpty() trị ưu tiên k.  findMin() tìm đối tượng có  Ứng dụng giá trị ưu tiên nhỏ nhất.  Quản lý băng thông Thực hiện được nếu hàng  Sử dụng trong thiết kế các không rỗng thuật toán (Huffman ) 3 diepht@vnu
  4. Minh họa Phép toán Output Hàng ưu tiên insert(5,A) - {(5,A)} insert(9,C) - {(5,A), (9,C)} insert(3,B) - {(3,B), (5,A), (9,C)} insert(7,D) - {(3,B), (5,A), (7,D), (9,C)} findMin() B {(3,B), (5,A), (7,D), (9,C)} findMinKey() 3 {(3,B), (5,A), (7,D), (9,C)} removeMin() - {(5,A), (7,D), (9,C)} size() 3 {(5,A), (7,D), (9,C)} findMin () A {(5,A), (7,D), (9,C)} removeMin() - {(7,D), (9,C)} removeMin() - {(9,C)} removeMin() - {} removeMin() “error” {} isEmpty() true {} 4 diepht@vnu
  5. Wikipedia: priority queue 5 diepht@vnu
  6. NIST’s DADS: priority queue 6 diepht@vnu
  7. Standard Template Library 7 diepht@vnu
  8. Nội dung chính 1. KDLTT hàng ưu tiên 2. Các phương pháp cài đặt 3. Ứng dụng: xây dựng mã Huffman 8 diepht@vnu
  9. Các phương pháp cài đặt findMin insert removeMin Mảng được sắp ? ? ? Mảng không sắp ? ? ? DSLK được sắp ? ? ? DSLK không sắp ? ? ? Cây TKNP ? ? ? Cây thứ tự bộ phận ? ? ? (heap) 9 diepht@vnu
  10. Cài đặt hàng ưu tiên bởi mảng Ví dụ Minh họa mảng Mảng được Q = {(3,B), (5,A), (7,D), (9,C)} 9,C 7,D 5,A 3,B sắp findMin() 9,C 7,D 5,A 3,B insert(8, E) 9,C 8,E 7,D 5,A 3,B removeMin() 9,C 8,E 7,D 5,A Mảng không Q = {(7,D), (3,B), (9,C), (5,A)} 7,D 3,B 9,C 5,A sắp findMin() 7,D 3,B 9,C 5,A insert(8, E) 7,D 3,B 9,C 5,A 8,E removeMin() 7,D 9,C 5,A 8,E 10 diepht@vnu
  11. Cài đặt hàng ưu tiên bởi cây tìm kiếm nhị phân 1. hàng ưu tiên 7,D 2. findMin() 7,D 3,B 9,C 3,B 9,C 2,F 5,A 8,E 2,F 5,A 8,E 7,D 3. insert(4,G) 4. removeMin() 7,D 3,B 9,C 3,B 9,C 2,F 5,A 8,E 2,F 5,A 8,E 4,G 4,G 11 diepht@vnu
  12. Cây thứ tự bộ phận (heap)  Cây nhị phân hoàn toàn  có tất cả các mức của cây đều 0 2 không thiếu đỉnh nào, trừ mức thấp nhất được lấp đầy kể từ bên trái 1 5 2 3  Min heap là một cây nhị phân 5 hoàn toàn với tính chất 3 9 4 7 8  khóa của một đỉnh bất kỳ nhỏ hơn hoặc bằng khóa của các đỉnh con của nó 2 5 3 9 7 8  Max heap  Cài đặt heap  có thể dùng cấu trúc liên kết (con trỏ)  có thể dùng mảng  Độ cao của heap là log(n) 12 diepht@vnu
  13. Cài đặt hàng ưu tiên bởi heap  findMin? 0 2,F  insert? 1 5,A 2 3,B  removeMin? 5 3 9,C 4 7,D 8,E 2,F 5,A 3,B 9,C 7,D 8,E 13 diepht@vnu
  14. Xen thêm vào heap  Phép insert của hàng ưu tiên tương ứng với phép 2 xen thêm một phần tử có 5 z 6 khóa k vào heap z  Thuật toán 9 7  Tìm tới vị trí z để đưa phần tử mới vào (là đỉnh cuối insertion node mới) 2  Lưu phần tử có khóa k vào z  Khôi phục tính chất thứ tự 5 6 bộ phận của heap z z 9 7 1 14 diepht@vnu
  15. Thuật toán upheap  Sau khi xen thêm một khóa k mới, heap có thể mất đi tính chất thứ tự bộ phận  Thuật toán upheap khôi phục lại tính chất này bằng cách đảo chỗ k dọc theo đường đi từ đỉnh mới hướng tới gốc  Upheap dừng lại khi k tiến tới gốc hoặc một đỉnh có khóa của cha ≤ k  Vì heap có độ cao O(log n), upheap thực hiện trong thời gian O(log n) 2 1 5 1 5 2 z z 9 7 6 9 7 6 15 diepht@vnu
  16. Loại một phần tử khỏi heap  Phép removeMin của hàng ưu tiên tương ứng 2 với phép loại gốc của 5 6 heap w  Thuật toán 9 7  Thay thế gốc bằng đỉnh cuối cùng w đỉnh cuối  Giải phóng đỉnh w 7  Khôi phục tính chất thứ tự bộ phận của heap 5 6 w 9 16 diepht@vnu
  17. Thuật toán downheap  Sau khi thay thế đỉnh gốc với đỉnh cuối (có khóa k), heap có thể mất đi tính chất thứ tự bộ phận  Thuật toán downheap khôi phục lại tính chất này bằng cách đảo chỗ đỉnh có khóa k dọc theo đường đi từ gốc xuống  Downheap dừng khi k tiến tới một lá hay một đỉnh có các khóa con ≥ k  Do heap có độ cao O(log n), downheap thực hiện trong thời gian O(log n) 7 5 5 6 7 6 w w 9 9 17 diepht@vnu
  18. Cập nhật con trỏ tới đỉnh cuối  Dùng trong cài đặt heap bằng cấu trúc liên kết  Có thể tìm chỗ cho đỉnh sẽ thêm vào bằng cách đi theo hành trình gồm O(log n) đỉnh  Đi lên tới khi gặp một con trái hoặc gặp gốc  Nếu gặp một con trái thì chuyển sang con phải  Đi xuống tới khi gặp một lá  Áp dụng thuật toán tương tự cho cập nhật con trỏ tới đỉnh cuối trong phép loại bỏ một đỉnh 18 diepht@vnu
  19. Minh họa cài đặt hàng ưu tiên last comp (4,C) (5,A) (6,Z) (15,K) (9,F) (7,Q) (20,B) (16,X) (25,J) (14,E) (12,H) (11,S) (18,W) 19 diepht@vnu
  20. insert(2,T) (4,C) (5,A) (6,Z) (15,K) (9,F) (7,Q) (20,B) (16,X) (25,J) (14,E) (12,H) (11,S) (18,W) 20 diepht@vnu
  21. insert(2,T) (4,C) (5,A) (6,Z) (15,K) (9,F) (7,Q) (20,B) (16,X) (25,J) (14,E) (12,H) (11,S) (18,W) (2,T) 21 diepht@vnu
  22. insert(2,T) (4,C) (5,A) (6,Z) Đảo (15,K) (9,F) (7,Q) (20,B) (2,T) và (20,B) (16,X) (25,J) (14,E) (12,H) (11,S) (18,W) (2,T) 22 diepht@vnu
  23. insert(2,T) (4,C) Đảo (2,T) và (5,A) (6,Z) (6,Z) (15,K) (9,F) (7,Q) (2,T) (16,X) (25,J) (14,E) (12,H) (11,S) (18,W) (20,B) 23 diepht@vnu
  24. insert(2,T) Đảo (4,C) (2,T) và (4,C) (5,A) (2,T) (15,K) (9,F) (7,Q) (6,Z) (16,X) (25,J) (14,E) (12,H) (11,S) (18,W) (20,B) 24 diepht@vnu
  25. insert(2,T) (2,T) (5,A) (4,C) (15,K) (9,F) (7,Q) (6,Z) (16,X) (25,J) (14,E) (12,H) (11,S) (18,W) (20,B) Sau thời gian O (log n) thì cây lại thành một heap 25 diepht@vnu
  26. removeMin() (4,C) (5,A) (6,Z) (15,K) (9,F) (7,Q) (20,B) (16,X) (25,J) (14,E) (12,H) (11,S) (18,W) 26 diepht@vnu
  27. removeMin() (4,C) (5,A) (6,Z) (18,W) (15,K) (9,F) (7,Q) (20,B) (16,X) (25,J) (14,E) (12,H) (11,S) 27 diepht@vnu
  28. removeMin() Đảo (18,W) (18,W) và (5,A) (5,A) (6,Z) (15,K) (9,F) (7,Q) (20,B) (16,X) (25,J) (14,E) (12,H) (11,S) 28 diepht@vnu
  29. removeMin() (5,A) (18,W) Đảo (18,W) (6,Z) và (9,F) (15,K) (9,F) (7,Q) (20,B) (16,X) (25,J) (14,E) (12,H) (11,S) 29 diepht@vnu
  30. removeMin() (5,A) (9,F) (6,Z) (15,K) (18,W) Đảo (18,W) (7,Q) (20,B) và (12,H) (16,X) (25,J) (14,E) (12,H) (11,S) 30 diepht@vnu
  31. removeMin() Đỉnh cuối (5,A) (9,F) (6,Z) (15,K) (12,H) (7,Q) (20,B) (16,X) (25,J) (14,E) (18,W) (11,S) 31 diepht@vnu
  32. Độ phức tạp  Độ phức tạp không gian  Cài bằng cấu trúc liên kết (dùng con trỏ): O(n)  Cài bằng cấu trúc vector (mảng): tỉ lệ với N (cỡ của mảng)  Độ phức tạp thời gian Phép toán Thời gian size, isEmpty O (1) findMin, findMinKey O (1) insert O (log n) removeMin O (log n) 32 diepht@vnu
  33. Tổng kết findMin insert removeMin Mảng được sắp O(1) O(n) O(1) Mảng không sắp O(n) O(1) O(n) DSLK được sắp O(1) O(n) O(1) DSLK không sắp O(n) O(1) O(n) Cây TKNP O(h) O(h) O(h) Cây thứ tự bộ phận O(1) O(logn) O(logn) (heap) 33 diepht@vnu
  34. Nội dung chính 1. KDLTT hàng ưu tiên 2. Các phương pháp cài đặt 3. Ứng dụng: xây dựng mã Huffman 34 diepht@vnu
  35. Nén dữ liệu  Giả sử cần nén một tệp dữ liệu Chữ cái a b c d e f chứa 100000 ký tự từ bảng 6 chữ (1) cái (từ a đến f). Từ mã 000 001 010 011 100 101  Mã độ dài giống nhau (1) Chữ cái a b c d e f . biểu diễn mỗi chữ cái bởi 3 bit Tần suất (K) 45 13 12 16 9 5 (thay vì 8 bit như thường lệ) (2) . tỉ lệ nén = 3/8 Từ mã 0 101 100 111 1101 1100  Mã độ dài khác nhau (2) . dùng khi ta biết tần suất của các . Chú ý: không có mã nào được làm chữ cái tiền tố của mã khác . gán mã ngắn nhất cho chữ cái xuất gọi là mã tiền tố (prefix code) hiện nhiều nhất o mục đích: phục vụ giải nén . kích thước file nén: o . (45×1 + 13×3 + 12×3 + 16×3 + 9×4 + 5×4) Bài toán: xây dựng mã tiền tố với tỉ × 1000 = 224 000 bits lệ nén thấp nhất . tỉ lệ nén = 0.28 o Lời giải: mã Huffman 35 diepht@vnu
  36. Mã Huffman 100  Biểu diễn mã tiền tố dưới dạng cây nhị phân 0 1  tại mỗi đỉnh, nhánh trái được 45 55 gắn nhãn là 0, nhánh bên (a) phải được gắn nhãn là 1 0 1  mỗi ký tự được lưu trong một đỉnh lá 25 30  từ mã của mỗi ký tự là xâu bit 0 1 0 1 tạo thành từ các nhãn trên đường đi từ gốc tới đỉnh lá 12 13 14 16 chứa ký tự đó (c) (b) (d)  Thuật toán Huffman sử dụng 0 1 hàng ưu tiên để xây dựng mã tiền tố dưới dạng cây nhị phân 5 9 (f) (e)  Mã sinh ra gọi là mã Huffman Chữ cái a b c d e f Tần suất (K) 45 13 12 16 9 5 Từ mã 0 101 100 111 1101 1100 36 diepht@vnu
  37. Thuật toán Huffman  Với mỗi ký tự xuất hiện trong xâu Algorithm HuffmanCoding(S,F) nguồn, ta tạo ra một đỉnh chứa ký Input: Bảng chữ cái S và bảng các tần tự đó suất F Output: cây Huffman  gắn với giá trị ưu tiên bằng tần suất Tạo ra một đỉnh cho mỗi ký tự trong S hởi tạo hàng ưu tiên P chứa  K các đỉnh Từ tập các cây chỉ có một đỉnh, tại này mỗi bước ta kết hợp hai cây for i=0 to n-1 do thành một cây v1  P.removeMin()  đỉnh cha sẽ gắn với giá trị ưu tiên v  P.removeMin() bằng tổng độ ưu tiên các con 2 Tạo ra đỉnh v mới với  ta cần chọn hai cây nhị phân có  mức ưu tiên nhỏ nhất để kết hợp v.leftChild v1 thành một dùng hàng ưu tiên. v.rightChild  v2 v.f  v1.f + v2.f P.insert(v) 37 diepht@vnu
  38. 45 (a) 12 13 16 (c) (b) (d) 5 9 (f) (e) 38 diepht@vnu
  39. 45 (a) 12 13 14 16 (c) (b) (d) 0 1 5 9 (f) (e) 39 diepht@vnu
  40. 45 (a) 25 0 1 12 13 14 16 (c) (b) (d) 0 1 5 9 (f) (e) 40 diepht@vnu
  41. 45 (a) 25 30 0 1 0 1 12 13 14 16 (c) (b) (d) 0 1 5 9 (f) (e) 41 diepht@vnu
  42. 45 55 (a) 0 1 25 30 0 1 0 1 12 13 14 16 (c) (b) (d) 0 1 5 9 (f) (e) 42 diepht@vnu
  43. 100 0 1 45 55 (a) 0 1 25 30 0 1 0 1 12 13 14 16 (c) (b) (d) 0 1 5 9 (f) (e) 43 diepht@vnu
  44. Mục tiêu bài học 1. KDLTT hàng ưu tiên 2. Các phương pháp cài đặt 3. Ứng dụng: xây dựng mã Huffman 44 diepht@vnu
  45. Chuẩn bị tuần tới  Lý thuyết: Đọc chương 16 giáo trình (Thiết kế thuật toán)  Thực hành: Bảng băm 45 diepht@vnu