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. 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: Bài 11 - Hoàng Thị Điệp (2014)Bài 11: Hàng ưu tiênGiảng viên: Hoàng Thị ĐiệpKhoa Công nghệ Thông tin – Đại học Công NghệCấu trúc dữ liệu và giải thuậtHKI, 2013-2014Nội dung chínhKDLTT hàng ưu tiên2. Các phương pháp cài đặt3. Ứng dụng: xây dựng mã Huffman1.2diepht@vnuKDLTT hàng ưu tiên(priority queue) Là tập hợp trong đó mỗiphần tử là một cặp (giá trịưu tiên, đối tượng) ta có thể so sánh được cácgiá 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àngkhông rỗng3 removeMin() loại bỏ và trảvề đối tượng có giá trị ưutiên nhỏ nhất. Thực hiệnđược nếu hàng không rỗng. findMinKey() tìm giá trị ưutiê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ácthuật toán (Huffman…)diepht@vnuMinh họa4Phép toánOutputHàng ưu tiêninsert(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@vnuWikipedia: priority queue5diepht@vnu