PriorityQueue 抛出 class 强制转换异常

Question

PriorityQueue 添加方法在执行时抛出 class 转换异常（MyVertex 无法转换为 java.lang.Comparable）。

一些MyVertex类型的对象正确插入，一些抛出异常，无法找到它们之间的差异。

参见java中附加的代码行：

 PriorityQueue<Vertex> pq = new PriorityQueue<>();
 for (Edge edge : vertex.getEdges()) {
      pq.add(edge.getTo());
 }

预期：方法 pq.add() 不应抛出异常。

Answer 1

实现Comparable接口并在Vertexclass中覆盖ComapareTo以满足优先级队列的排序。

正如 java 文档所说 - add 如果指定元素无法根据优先级队列的顺序与当前在此优先级队列中的元素进行比较，则抛出 ClassCastException.
正如您之前所说的那样，这是因为当 priorityQueues 的大小为 0（添加第一个元素时）时，add 调用不会抛出 ClassCastException。为了测试这一点，在调用 for 循环之前打印 vertex.getEdges().size() 的大小。如果大小似乎大于 0，则将抛出 ClassCastException。

当大小不为零时，将调用筛选操作，因为此处优先级队列中的底层 data_structure 是一个堆。

您看到的异常是由 sift-up 触发的，因为内部筛选需要您的元素实现 Comparable。而sift-up是在优先级队列大小不为0，或者有后续元素加入时调用。

注：

堆应该满足堆属性：如果P是C的父节点，然后 P 的键（值）大于或等于（在最大堆）或小于或等于（在最小堆中）C.
的键
向上筛选：根据需要在树中向上移动一个节点；习惯于插入后恢复堆状态。称为“筛选”，因为节点向上移动树，直到达到正确的水平，就像在筛子中一样。

PriorityQueue throwing class cast exception