Bài giảng "Cấu trúc dữ liệu và giải thuật - Bài 10: Hàng ưu tiên" cung cấp cho người học các kiến thức: Kiểu dữ liệu trừu tượng hàng ưu tiên, các phương pháp cài đặt, ứng dụng xây dựng mã Huffman. nội dung chi tiết. | HK I, 2012-2013 Bài 10: 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ệ 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 diepht@vnu INT2203/w11 2 KDLTT hàng ưu tiên (priority queue) • Là tập hợp trong đó mỗi phần tử là một cặp (giá trị ưu tiên, đối tượng) – removeMin() loại bỏ và trả về đối tượng có giá trị ưu tiên nhỏ nhất. Thực hiện được nếu hàng không rỗng. – findMinKey() tìm giá trị ưu tiên nhỏ nhất .Thực hiện được nếu hàng không rỗng – size() – isEmpty() – ta có thể so sánh được các giá trị ưu tiên • Các phép toán – insert(k, o) xen vào hàng ưu tiên đối tượng o có giá trị ưu tiên k. – findMin() tìm đối tượng có giá trị ưu tiên nhỏ nhất .Thực hiện được nếu hàng không rỗng diepht@vnu • Ứng dụng INT2203/w11 – Quản lý băng thông – Sử dụng trong thiết kế các thuật toán (Huffman ) 3 Minh họa diepht@vnu 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 {} INT2203/w11 4 Wikipedia: priority .
