tailieunhanh - 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. | 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 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) – 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 – 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 ) 3 Minh h a Phép toán 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() diepht@vnu Output true {} 4 Wikipedia: priority .