java - 使用priorityQueue实现具体的java MaxHeap

Question

我将使用priorityQueue实现特定的java maxHeap，如下所示:假设我有一个“Customer”类，它有一个双变量名称“marginalGain”。

PriorityQueue<Customer> marginalGainHeap=new PriorityQueue<Customer>();

如何使用“marginalGain”变量的自然顺序堆化“marginalGainHeap”？是否可以使用 PriorityQueue 或者我需要自己重新实现 MaxHeap？

问候。

Answer 1

您可以使用 PriorityQueue，但值得记住的是，只有第一个条目才会被排序。您很可能希望 TreeSet 作为 SortedSet。

在任何情况下，您都需要使客户具有可比性，或者更有可能提供更好的解决方案，最好创建 Comparator<Customer>因为您可能想要按多个订单对客户进行排序。注意:您需要对所有客户下订单，即即使他们的 marginGain 相同，您也需要给他们下订单。

您可以像这样将比较器与 PriorityQueue 一起使用。

PriorityQueue<Customer> pq = new PriorityQueue<Customer>(new Comparator<Customer>() {
    public int compare(Customer c1, Customer c2) {
       return Double.compare(c1.getMarginGain(), c2.getMarginGain());
    }
});

PriorityQueue 的一个优点是您不必确保比较器不会针对不同的客户返回 0(在 TreeSet 中，它会将这些视为重复项并丢弃它们)