Calendar Queue : A Fast O(1) Priority Queue Implementation for the Simulation Event Set Problem

Chúng ta thường được học về hàng đợi ưu tiên cài đặt bằng cấu trúc dữ liệu Heap, tuy nhiên đây không phải là cách duy nhất để cài đặt hàng đợi ưu tiên và như ta được học mặc dù việc cài đặt bằng cấu trúc dữ liệu Heap thì các thao các như insert hay delete phần tử cũng đã rất nhanh rồi, tuy nhiên cài đặt hàng đơi ưu tiên bằng cấu trúc dữ liệu Heap cũng chưa phải cách nhanh nhất.

Chúng ta có rất nhiều các cài đặt hàng đợi ưu tiên khác mang lại hiệu quả cao hơn việc sử dụng cấu trúc dữ liệu Heap, ví dụ như sử dụng cây S-Play, Calendar Queue,...

Việc cài đặt hàng đợi ưu tiên bằng Calendar Queue mang lại hiệu quả rất tốt, nó được đánh giá là một trong những phương pháp tốt nhất để cài đặt hàng đợi ưu tiên.

Nếu bạn muốn tìm hiểu về Calendar Queue để sắp xếp cho số lượng lớn các sự kiện thì có thể tham khảo qua bài báo Calendar Queue : A fast O(1) priority queue implementation for the simulation event set problem

Mình có một vài code Calendar Queue bằng C TẠI ĐÂY, mọi người có thể tham khảo nha.

0 Bình luận:

Đăng nhận xét