Bài giảng Cơ sở dữ liệu giải thuật: Bài 10 - Hàng ưu tiên

Mục tiêu của bài giảng Cơ sở dữ liệu giải thuật: Bài 10 - Hàng ưu tiên là nhằm giúp cho các bạn biết đượ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 tham khảo bài giảng để hiểu rõ hơn về những nội dung này.
Nội dung trích xuất từ tài liệu:
Bài giảng Cơ sở dữ liệu giải thuật: Bài 10 - Hàng ưu tiênBài 10: Hàng ưu tiênGi ng viên: Hoàng Th i pKhoa Công ngh Thông tin –i h c Công NghM c tiêu bài h c1. KDLTT hàng ưu tiên2. Các phương pháp cài t3.ng d ng: xây d ng mã Huffmandiepht@vnu2KDLTT hàng ưu tiên(priority queue)• Là t p h p trong ó m i ph nt 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êni 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 ư cn u hàng không r ngdiepht@vnu– removeMin() lo i b và tr vi tư ng có giá tr ưu tiênnh nh t. Th c hi n ư c n uhàng không r ng.– findMinKey() tìm giá tr ưu tiênnh nh t .Th c hi n ư c n uhà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…)3Minh h aPhép toánHà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()diepht@vnuOutputtrue{}4Wikipedia: priority queuediepht@vnu5