Làm thế nào để bảo toàn thứ tự các phần tử có cùng mức độ ưu tiên trong hàng đợi ưu tiên được thực hiện dưới dạng đống nhị phân?

Question

Tôi đã tạo một đống nhị phân, đại diện cho hàng đợi ưu tiên. Nó chỉ là thuật toán nổi tiếng cổ điển. Heap này lên lịch trình theo thứ tự thời gian của các sự kiện khác nhau (khóa sắp xếp là thời gian).

Nó hỗ trợ 2 thao tác: Chèn và Xóa. Mỗi khóa của nút của heap lớn hơn hoặc bằng mỗi nút con của nó. Tuy nhiên, việc thêm các sự kiện với cùng một khóa không bảo vệ thứ tự chúng được thêm vào, bởi vì mỗi lần sau khi Remove hoặc Insert được gọi, các thủ tục heap-up và heap-down phá vỡ thứ tự.

Câu hỏi của tôi là: điều gì cần được thay đổi trong thuật toán cổ điển để duy trì thứ tự của các nút có cùng mức độ ưu tiên?

Answer 1

Một giải pháp là thêm thời gian của thuộc tính chèn vào phần tử được chèn. Đó có thể chỉ là một bộ đếm đơn giản tăng lên mỗi khi một phần tử mới được chèn vào heap. Sau đó, khi hai phần tử đều bằng nhau, hãy so sánh thời gian chèn.

Answer 2

Nếu các phần tử được chèn vào thứ tự thời gian và thứ tự này được duy trì (ví dụ bằng cách "nối thêm" thay vì "chèn" và "remove_and_pack" thay vì chỉ "xóa"), bạn có thể sử dụng địa chỉ bộ nhớ (truyền tới một số nguyên không dấu 32 hoặc 64 bit tùy thuộc vào môi trường) của phần tử làm bước so sánh cuối cùng. Các yếu tố ban đầu sẽ có địa chỉ số thấp hơn các địa chỉ sau.

Answer 3

Theo như tôi biết, heaps không bao giờ được xây dựng để bảo tồn trật tự (đó là lý do tại sao "phân loại đống" là đáng chú ý cho không phải là một loại ổn định).

Tôi hiểu rằng những gì bạn đang hỏi là liệu một thuật toán nhỏ có thể thay đổi được điều này (đó không phải là giải pháp "dấu thời gian" đáng tin cậy cũ). Tôi không nghĩ là có thể.

Những gì tôi đã gợi ý là một số phiên bản này:

• giữ cùng "chèn";

• sửa đổi "xóa" để đảm bảo thứ tự nhất định trên các yếu tố có mức độ ưu tiên nhất định.

Để làm điều này, trong đống xuống, thay vì trao đổi các yếu tố xuống cho đến khi trật tự được bảo tồn: hoán đổi một yếu tố xuống cho đến khi nó là sự kết thúc của một arborescence của các yếu tố của giá trị như nhau, luôn luôn chọn để đi ở bên phải khi bạn có thể.

Thật không may vấn đề với điều này là bạn không biết nơi chèn sẽ thêm một yếu tố của một ưu tiên nhất định: nó có thể kết thúc ở bất cứ nơi nào trong cây. Thay đổi điều này sẽ là, tôi tin rằng, nhiều hơn chỉ là một tinh chỉnh cho cấu trúc.