Tại sao hàng đợi ưu tiên/heap được triển khai là 0 là ưu tiên cao nhất? Tôi giả sử tôi đang bỏ lỡ một số nguyên tắc toán học chính. Như tôi đã thực hiện hàng đợi ưu tiên của riêng tôi gần đây nó có vẻ dễ dàng hơn để viết các chức năng chèn nếu ưu tiên đi lên với giá trị số nguyên, nhưng dường như mọi người thông minh hơn tôi nghĩ rằng nó nên đi theo cách khác.Tại sao hàng đợi ưu tiên chủ yếu sử dụng 0 làm ưu tiên quan trọng nhất?
Bất kỳ ý tưởng nào?
Hàng đợi ưu tiên nhất được triển khai dưới dạng fibonacci heap hoặc tương tự. Cấu trúc dữ liệu đó hỗ trợ giải nén tối thiểu theo thời gian cố định, làm cho nó tự nhiên làm cho 0 là ưu tiên cao nhất, và lấy các phần tử ra khỏi hàng đợi bằng cách giải nén tối thiểu.
Tôi không nghĩ có bất kỳ lý do thiết kế nào cho nó. Nó có lẽ chỉ vì hầu hết các lập trình viên được sử dụng để suy nghĩ của 0 là yếu tố đầu tiên. Một lý do khác có thể là do các điều tra viên bắt đầu từ 0 để giá trị số nguyên "Cao nhất" được xác định trước là 0.
Nếu nó tăng lên, bạn có thể đặt bất kỳ thứ gì lên mức ưu tiên cao nhất? (+1 cho câu trả lời rossfab của :)
Như một phản ví dụ, trong những gì là chắc chắn một trong những có sẵn hầu hết (nếu không được sử dụng) triển khai hàng đợi ưu tiên, cụ thể là STL của std::priority_queue, yếu tố top() là một số lượng cao nhất theo operator<. Tất nhiên tất cả mọi người được sử dụng để quy ước thấp nhất trong thứ tự sắp xếp được trước hàng đợi vì vậy điều này bắt rất nhiều người ra lần đầu tiên họ sử dụng nó.
Lý do thường là cách khác là hàng đợi ưu tiên được sử dụng để thực hiện các thuật toán như Dijkstra và A *, nơi ưu tiên là khoảng cách đến nút và bạn muốn xử lý các nút gần hơn trước.
Không có gì vốn có về hàng đợi ưu tiên khiến 0 trở thành lựa chọn tốt hơn cho ưu tiên hàng đầu. Tuy nhiên, đối với một người viết một bản thực thi có thể tái sử dụng, bạn sẽ phải chọn thứ gì đó và 0 được xác định rõ ràng bất kể loại giá trị điểm tích phân hoặc dấu phẩy bạn sử dụng cho ưu tiên của bạn. Ngay cả khi viết bài thực hiện riêng, nếu bạn quyết định chỉ cần 256 mức ưu tiên và sử dụng char chưa được ưu tiên làm ưu tiên hàng đầu của bạn và 255 là ưu tiên hàng đầu của bạn, thì bạn sẽ cần phải xem xét cẩn thận tất cả mã của mình nếu bạn quyết định bạn cần nhiều cấp độ hơn.
Đã học được điều gì đó mới mẻ. Cảm ơn! –
Điều này là gây hiểu nhầm: tất cả các đống tôi từng nghe về hỗ trợ * xác định * tối thiểu trong thời gian không đổi; nhưng * loại bỏ * phần tử tối thiểu (do đó làm cho phần tử nhỏ thứ hai trở thành tối thiểu mới) luôn yêu cầu thời gian 'O (log (n))'. Điều này khá cơ bản; nếu không bạn có thể sử dụng heap đó để tạo một thuật toán phân loại 'O (n)'. Các lợi thế hiệu suất của một đống heap (trên đống nhị phân đơn giản) là trong các hoạt động khác, không phải là hai hoạt động tiêu chuẩn này. –
Ngoài ra, câu trả lời này thậm chí không giải quyết được câu hỏi! Dãy Fibonnacci cũng có thể hỗ trợ giải nén tối đa trong thời gian không đổi - nó chỉ là một quy ước. –