Đang chuẩn bị liên kết để tải về tài liệu:
CHƯƠNG 10: HÀNG ƯU TIÊN

Trong các chương trước chúng ta đã nghiên cứu KDLTT từ điển. Từ điển là một tập đối tượng dữ liệu, mỗi đối tượng được gắn với một giá trị khóa, và các phép toán tìm kiếm, xen, loại trên từ điển được tiến hành khi được cung cấp một giá trị khóa. Trong chương này chúng ta sẽ đưa ra KDLTT hàng ưu tiên. | phụ thuộc tham biến kiểu Item, trong đó Item là kiểu của các phần tử trong hàng ưu tiên. Các phần tử trong hàng ưu tiên chứa một thành phần là giá trị ưu tiên (priority), và để đơn giản cho cách viết ta giả thiết rằng, có thể truy cập trực tiếp tới giá trị ưu tiên của các phần tử. Chúng ta có thể cài đặt hàng ưu tiên bởi mảng động, như chúng ta đã làm khi cài đặt danh sách (xem mục 4.3). Song để tập trung sự chú ý tới các kỹ thuật được sử dụng trong các phép toán hàng ưu tiên, chúng ta cài đặt hàng ưu tiên bởi mảng tĩnh data. Cài đặt bởi mảng động để lại cho độc giả, xem như bài tập. Lớp PriQueue chứa hai hàm kiến tạo, hàm kiến tạo mặc định làm nhiệm vụ tạo ra một hàng ưu tiên rỗng, và một hàm kiến tạo khác xây dựng nên hàng ưu tiên từ các dữ liệu đã được lưu trong một mảng theo phương pháp trong mục 10.3.2. Các hàm thành phần còn lại là các hàm thực hiện các phép toán trên hàng ưu tiên. Một điều cần lưu ý là, chúng ta đưa vào lớp PriQueue một hàm ẩn ShiftDown(int i), hàm này thực hiện bước hai trong thuật toán DeleteMin. Hàm này được sử dụng để cài đặt hàm kiến tạo thứ hai và hàm DeleteMin.