tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật: Bài 11 - Hoàng Thị Điệp (2014)

Bài giảng "Cấu trúc dữ liệu và giải thuật - Bài 11: Hàng ưu tiên" cung cấp cho người học các kiến thức: KDLTT 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. | 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 Nội dung chính 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 1. 2 diepht@vnu 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) 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 3 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() Ứng dụng Quản lý băng thông Sử dụng trong thiết kế các thuật toán (Huffman ) diepht@vnu Minh họa 4 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 {} diepht@vnu Wikipedia: priority .