java - CompareTo 返回值不正确

Question

首先，我必须提到的是，在阅读了大量问题和教程并观看了一些视频后，问题仍然没有解决。

我是一名Java中级程序员，我编写了一些用于比较优先级队列中的元素的代码，其中元素的保存方式类似于[Comparable element, intpriority]。显然，更高的优先级将被弹出。

问题是:我修改了代码，使第一个元素具有最高优先级，但它不起作用!我已经缩小了范围，当比较前 2 个元素时，compareTo 方法返回 0，但它不应该返回 0，因此代码失败!

这个类的入栈时间为 O(1)，出栈时间为 O(n):

public class PriorityQueueU<T> 
    {
            public class PriorityPair implements Comparable
            {
                public Comparable  element;
                public Comparable  priority;

                public PriorityPair(Comparable  element, int  priority){
                    this.element = element; 
                    this.priority = priority; 
                }

                public Comparable<T> getElemet(){
                    return this.element; 
                }

                public Comparable<T> getPriority(){
                    return this.priority; 
                }

                public int compareTo(Comparable  a)
                {
                    PriorityPair p2 = (PriorityPair)a;
                    return ((Comparable)priority).compareTo(p2.priority);
                }

                public String toString(){

                    String s1 = this.element.toString(); 
                    String s2 = this.priority.toString(); 
                    String res = "[ " + s1 + ", " +  s2 + " ]"   ;
                    return res; 
                }

                public int compareTo(Object o)
                {
                    // TODO Auto-generated method stub
                    return 0;
                }

            }
            private LinkedList data;

            public PriorityQueueU()
            {
                data = new LinkedList();
            }


            public void pushUnsorted(Comparable<T>  o, int priority)
            {
                PriorityPair paired = new PriorityPair(o, priority);  
                data.addLast(paired);
            }

            public Comparable  popUnsorted()
            {


                int index = 0; 

                for (int i = 0; i < this.data.size() - 1; i++)
                {
                    if (((PriorityPair) this.data.get(i)).compareTo(this.data.get(i + 1)) < 0)
                    {
                        index = i + 1; 
                    }
                }

                PriorityPair pp = (PriorityQueueU<T>.PriorityPair) this.data.get(index); 
                this.data.deleteIt(index);
                return pp.getElemet(); 
            }




            public String toString(){
                return this.data.toString();  
            }

        }
}

这是测试行为的代码:

 PriorityQueueU<T> unSortedPQ = new PriorityQueueU<>();


            unSortedPQ.pushUnsorted( (Comparable<T>) "a", 1000);
            unSortedPQ.pushUnsorted((Comparable<T>) "b", 200);
            unSortedPQ.pushUnsorted((Comparable<T>) "j", 900);
            unSortedPQ.pushUnsorted((Comparable<T>) "r", 9);
            unSortedPQ.pushUnsorted((Comparable<T>) "z", 6);

            System.out.println("the UNsorted priority Q: ");
            System.out.println(unSortedPQ);

            System.out.println("*#------------------END OF PUSH-----------------#*");
            System.out.println();



            System.out.println("the priority Q: " + unSortedPQ);
            System.out.println("popped item is: " + unSortedPQ.popUnsorted());

    //      System.out.println("top of the priority queue is: " + uPriorityQueueU.top());
            System.out.println();

            System.out.println("the UNsorted priority Q: ");
            System.out.println(unSortedPQ);

            System.out.println("*#------------------END OF POP-----------------#*");
            System.out.println();

非常感谢。

附注请记住，也许我错了，问题出在其他地方!当前行为:它弹出 j，它是列表中第二高的元素。我已经知道，弹出时，该元素也必须从优先级队列中删除，该队列存储在链表中。我确保链接列表中的删除操作正确，但如有必要，请毫不犹豫地索取代码。

Answer 1

为了使 compareTo 工作，您应该实现 Comparable 接口(interface)提供的方法。

public interface Comparable<T> {
    public int compareTo(T o);
}

正如我们从上面的代码中看到的，Copmarable 支持泛型。如果您没有指定要比较的对象类型(保持原样)，它将默认为 Object，它会执行此操作(来自您的代码):

public int compareTo(Object o)
{
   // TODO Auto-generated method stub
   return 0;
}

因此，您要么使用泛型，要么为 compareTo(Object o) 编写逻辑。