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

Bài 10: Hàng ưu tiên<br /> Gi ng viên: Hoàng Th i p<br /> Khoa Công ngh Thông tin –<br /> i h c Công Ngh<br /> <br /> M c tiêu bài h c<br /> 1. KDLTT hàng ưu tiên<br /> 2. Các phương pháp cài t<br /> 3.<br /> ng d ng: xây d ng mã Huffman<br /> <br /> diepht@vnu<br /> <br /> 2<br /> <br /> KDLTT hàng ưu tiên<br /> (priority queue)<br /> • Là t p h p trong ó m i ph n<br /> t là m t c p (giá tr ưu tiên,<br /> i tư ng)<br /> – ta có th so sánh ư c các giá tr<br /> ưu tiên<br /> <br /> • Các phép toán<br /> – insert(k, o) xen vào hàng ưu tiên<br /> i tư ng o có giá tr ưu tiên k.<br /> – findMin() tìm i tư ng có giá tr<br /> ưu tiên nh nh t .Th c hi n ư c<br /> n u hàng không r ng<br /> <br /> diepht@vnu<br /> <br /> – removeMin() lo i b và tr v<br /> i tư ng có giá tr ưu tiên<br /> nh nh t. Th c hi n ư c n u<br /> hàng không r ng.<br /> – findMinKey() tìm giá tr ưu tiên<br /> nh nh t .Th c hi n ư c n u<br /> hàng không r ng<br /> – size()<br /> – isEmpty()<br /> <br /> •<br /> <br /> ng d ng<br /> <br /> – Qu n lý băng thông<br /> – S d ng trong thi t k các<br /> thu t toán (Huffman…)<br /> <br /> 3<br /> <br /> Minh h a<br /> Phép toán<br /> <br /> Hàng ưu tiên<br /> <br /> insert(5,A)<br /> <br /> -<br /> <br /> {(5,A)}<br /> <br /> insert(9,C)<br /> <br /> -<br /> <br /> {(5,A), (9,C)}<br /> <br /> insert(3,B)<br /> <br /> -<br /> <br /> {(3,B), (5,A), (9,C)}<br /> <br /> insert(7,D)<br /> <br /> -<br /> <br /> {(3,B), (5,A), (7,D), (9,C)}<br /> <br /> findMin()<br /> <br /> B<br /> <br /> {(3,B), (5,A), (7,D), (9,C)}<br /> <br /> findMinKey()<br /> <br /> 3<br /> <br /> {(3,B), (5,A), (7,D), (9,C)}<br /> <br /> removeMin()<br /> <br /> -<br /> <br /> {(5,A), (7,D), (9,C)}<br /> <br /> size()<br /> <br /> 3<br /> <br /> {(5,A), (7,D), (9,C)}<br /> <br /> findMin ()<br /> <br /> A<br /> <br /> {(5,A), (7,D), (9,C)}<br /> <br /> removeMin()<br /> <br /> -<br /> <br /> {(7,D), (9,C)}<br /> <br /> removeMin()<br /> <br /> -<br /> <br /> {(9,C)}<br /> <br /> removeMin()<br /> <br /> -<br /> <br /> {}<br /> <br /> removeMin()<br /> <br /> “error”<br /> <br /> {}<br /> <br /> isEmpty()<br /> diepht@vnu<br /> <br /> Output<br /> <br /> true<br /> <br /> {}<br /> 4<br /> <br /> Wikipedia: priority queue<br /> <br /> diepht@vnu<br /> <br /> 5<br /> <br />