时间戳

首页 > 解决方案 > PriorityQueue 抛出类强制转换异常

java - PriorityQueue 抛出类强制转换异常

问题描述

PriorityQueue add 方法在执行时抛出类转换异常（MyVertex 不能转换为 java.lang.Comparable）。

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

请参阅Java中的附加代码行：

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

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

标签： javapriority-queueclasscastexceptioncomparable

解决方案

  1. 实现Comparable接口并覆盖类ComapareTo内部Vertex以满足优先级队列的排序。

    正如java doc所说 -add 如果指定的元素无法根据优先级队列的 ordering 与当前位于此优先级队列中的元素进行比较，则抛出 ClassCastException。

  2. 正如您之前所说的那样，它是因为当 priorityQueues 的大小为 0（添加第一个元素时）时，add 调用不会抛出 ClassCastException。为了测试这一点，在调用 for 循环之前打印vertex.getEdges().size(). 如果大小看起来大于 0，那就是ClassCastException抛出的时候。

当大小不为零时，将调用筛选操作，因为这里优先级队列中的底层数据结构是一个堆。

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

笔记：

  • 堆应该满足堆属性：如果 P 是 C 的父节点，那么 P 的键（值）要么大于或等于（在最大堆中）或小于或等于（在最小堆中） C的关键。

    sift-up：在树中向上移动一个节点，只要需要；用于在插入后恢复堆状态。称为“筛选”，因为节点向上移动树直到它到达正确的级别，就像在筛子中一样。

堆数据结构

推荐阅读