Trình lặp lặp tích hợp cho PriorityQueue của java không đi qua cấu trúc dữ liệu theo bất kỳ thứ tự cụ thể nào. Tại sao?

Question

Đây là trực tiếp từ Java Docs:

này lớp và iterator của mình thực hiện tất cả các phương pháp bắt buộc các giao diện Collection và Iterator. Iterator được cung cấp trong phương thức iterator() không được bảo đảm để duyệt qua các phần tử của hàng đợi ưu tiên theo bất kỳ thứ tự cụ thể nào. Nếu bạn cần traversal có trật tự, hãy xem xét sử dụng Arrays.sort (pq.toArray()).

Vì vậy, về cơ bản, PriorityQueue của tôi hoạt động tốt, nhưng in nó ra màn hình sử dụng phương pháp riêng của nó được xây dựng trong toString() khiến tôi thấy bất thường này trong hành động, và đã tự hỏi nếu ai đó có thể giải thích lý do tại sao nó là trình vòng lặp được cung cấp (và được sử dụng trong nội bộ) không đi qua PriorityQueue theo thứ tự tự nhiên của nó?

Answer 1

Do cấu trúc dữ liệu cơ bản không hỗ trợ. Một đống nhị phân chỉ được đặt một phần, với phần tử nhỏ nhất ở gốc. Khi bạn loại bỏ điều đó, heap được sắp xếp lại sao cho phần tử nhỏ nhất tiếp theo nằm ở gốc. Không có thuật toán truyền tải có trật tự hiệu quả nên không có thuật toán nào được cung cấp trong Java.

Answer 2

Lúc đầu tiên đoán, có thể là chuyển dữ liệu theo thứ tự lưu trữ. Để giảm thiểu thời gian chèn một mục vào hàng đợi, nó thường không lưu trữ tất cả các mục theo thứ tự được sắp xếp.

Answer 3

Vâng, như Javadoc đã nói, đó là cách nó được triển khai. Hàng đợi ưu tiên có thể sử dụng heap nhị phân làm cấu trúc dữ liệu cơ bản. Khi bạn xóa các mục, heap được sắp xếp lại để bảo toàn thuộc tính heap.

Thứ hai, không khôn ngoan để ràng buộc trong việc triển khai cụ thể (buộc phải sắp xếp thứ tự). Với việc triển khai hiện tại, bạn được tự do duyệt qua nó theo bất kỳ thứ tự nào và sử dụng bất kỳ triển khai nào.

Answer 4

Heaps nhị phân là cách hiệu quả để triển khai hàng đợi ưu tiên. Việc bảo đảm duy nhất về thứ tự mà một đống tạo ra là mục ở trên cùng có mức ưu tiên cao nhất (có thể nó là "lớn nhất" hoặc "nhỏ nhất" theo một số thứ tự). Heap là cây nhị phân có thuộc tính: Thuộc tính hình dạng: cây lấp đầy từ trên xuống dưới sang phải Thứ tự prperty: phần tử tại bất kỳ nút nào lớn hơn (hoặc nhỏ hơn nếu nhỏ nhất có ưu tiên cao nhất) so với hai các nút con. Khi trình vòng lặp truy cập tất cả các phần tử, nó có thể làm như vậy trong quá trình truyền tải bậc theo thứ tự, nghĩa là nó truy cập từng nút ở mỗi cấp lần lượt trước khi chuyển sang cấp độ tiếp theo. Vì bảo đảm duy nhất về thứ tự được thực hiện là một nút có mức độ ưu tiên cao hơn các nút con của nó, các nút ở mỗi cấp sẽ không theo thứ tự cụ thể.

Answer 5

Ưu tiênQueue được triển khai bằng cách sử dụng đống nhị phân. Một đống không phải là một cấu trúc được sắp xếp và nó được đặt một phần. Mỗi phần tử có một "ưu tiên" liên kết với nó. Sử dụng một heap để thực hiện một hàng đợi ưu tiên, nó sẽ luôn có phần tử ưu tiên cao nhất trong nút gốc của heap. do đó, trong hàng đợi ưu tiên, phần tử có mức độ ưu tiên cao được phân phối trước phần tử có mức độ ưu tiên thấp. Nếu hai phần tử có cùng mức độ ưu tiên, chúng được phân phối theo thứ tự của chúng trong hàng đợi. Heap được cập nhật sau mỗi lần xóa các phần tử để duy trì thuộc tính heap