tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật: Hàng đợi ưu tiên - Nguyễn Mạnh Hiển (HKI năm 2020-2021)

Bài giảng "Cấu trúc dữ liệu và giải thuật: Hàng đợi ưu tiên" cung cấp cho người học các kiến thức: Hàng đợi ưu tiên, cài đặt hàng đợi ưu tiên, đống nhị phân, cây nhị phân đầy đủ, cài đặt cây nhị phân đầy đủ, . | Hàng đợi ưu tiên Priority Queues Nguyễn Mạnh Hiển hiennm@ Hàng đợi ưu tiên Phần tử nhỏ nhất có độ ưu tiên cao nhất và sẽ được lấy ra đầu tiên. Chèn insert Thời gian O log N Xóa phần tử nhỏ nhất deleteMin Thời gian O log N Cài đặt hàng đợi ưu tiên Dùng danh sách liên kết insert dùng pushFront mất thời gian O 1 . deleteMin quét tìm rồi xóa min mất thời gian O N . Dùng cây nhị phân tìm kiếm insert và deleteMin mất thời gian O log N . Tuy nhiên cây nhị phân tìm kiếm quá phức tạp cho yêu cầu đơn giản hơn của hàng đợi ưu tiên. Đống nhị phân binary heap Là cách cài đặt phổ biến của hàng đợi ưu tiên. insert và deleteMin mất thời gian O log N . Đống nhị phân Gọi tắt là đống. Thỏa mãn 1. Là cây nhị phân đầy đủ. 2. Có tính chất thứ tự đống. Cây nhị phân đầy đủ Là cây nhị phân với tất cả các mức trừ mức dưới cùng đã được lấp đầy các nút từ trái sang phải. Số nút n 20 21 . 2h 1 1 2h h log n Mức 0 có 20 nút Mức 1 có 21 nút Mức 2 có 22 nút Mức h có ít nhất 1 nút h là chiều cao của cây Cài đặt cây nhị phân đầy đủ Lưu trữ các phần tử lần lượt từng mức vào vector v. Cha của v k là v k 2 . Con trái của v k là v 2k . Con phải của v k là v 2k 1 . vector v Tính chất thứ tự đống Với mọi nút X trên đống giá trị của X nhỏ hơn giá trị của các nút con trái và phải của X. Suy ra Phần tử nhỏ nhất trên đống nằm ở gốc. Không có thứ tự nào giữa các nút con của cùng một nút. 0 3 2 4 5 Cây nào là đống Cài đặt hàng đợi ưu tiên trong C template class BinaryHeap public BinaryHeap int capacity 100 Khởi tạo đống rỗng BinaryHeap const vector amp elems Dựng đống const T amp findMin Tìm phần tử nhỏ nhất ở gốc void insert const T amp x Chèn x vào đống void deleteMin Xóa phần tử nhỏ nhất ở gốc private int currentSize Số phần tử hiện có vector array Vector chứa các phần tử void buildHeap Giúp dựng đống trong hàm tạo void percolateDown int hole Giúp xóa min và dựng đống Chèn vào đống insert 14 Chèn vào đống insert x Tạo lỗ trống hole ở vị trí có sẵn tiếp theo trong đống x là giá trị của lỗ trống .