删除元素时 PriorityQueue 改变顺序
PriorityQueue changes order when removing an element
在不提供自定义比较器的情况下,优先级队列按升序插入元素,但是,在删除特定元素后,顺序会发生变化。
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(10);
pq.add(1);
pq.add(2);
pq.add(2);
pq.remove(2);
for(int x: pq) {
System.out.println(x);
}
//outputs: 1 10 2, instead of expected: 1 2 10
有什么想法吗?
谢谢。
不要像在 collections/arrays 上那样重复 PriorityQueue<T>
;使用 .poll()
,而不是:
while(pq.peek()!=null) {
System.out.println(pq.poll());
}
优先级队列是一种抽象数据类型,通常作为 Binary Heap 数据结构实现,而后者又(通常)用数组实现。
还有其他一些方法可以实现二叉堆,但是普通数组是最快、最简单、最好的方法。
数组如何表示二进制堆的示例,如下所示:
Queue order 未更改,在您的情况下;相反,您只是以错误的方式使用数据结构,仅通过传统的 for-each
/迭代方式对其进行迭代,就像在基本数组上进行迭代时一样,而不考虑您的优先级队列支持数组是未按其 ith 索引排序;相反,它将顶部元素保留在树的顶部(最小堆或最大堆的情况)并且您不能仅通过以传统方式对其进行迭代来获得 .poll()
效果。
这是因为 PriorityQueue 是最小堆的实现(默认在 Java 中),这意味着根元素将始终低于列表中的其他元素。
以你的问题为例:
- 插入10时,数组中索引1处的元素为10
- 当你插入 1 时,因为
1 < 10
位置 1 的元素现在是 1 而 10 它移动到索引 2
- 当你插入2时,因为
1 < 2
不需要移动元素,2被插入到索引3
- 当你插入 2 时,2 将小于 10,因为
10 > 2
需要一个移位,2 被插入到 2 并且 10 被写入索引 4
所有插入数组后看起来是这样的,同时查看下面的视频:
array: [NULL, 1, 2, 2, 10]
现在当你删除 2 时,10 需要移位,并且 10 被移回索引 2,并且数组的状态是 [NULL, 1, 10, 2]
这就是你在迭代时看到的输出.另外,检查在 PriorityQueue 中实现的 the following method,当您不提供 Comparator
.
时使用
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
在不提供自定义比较器的情况下,优先级队列按升序插入元素,但是,在删除特定元素后,顺序会发生变化。
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(10);
pq.add(1);
pq.add(2);
pq.add(2);
pq.remove(2);
for(int x: pq) {
System.out.println(x);
}
//outputs: 1 10 2, instead of expected: 1 2 10
有什么想法吗?
谢谢。
不要像在 collections/arrays 上那样重复 PriorityQueue<T>
;使用 .poll()
,而不是:
while(pq.peek()!=null) {
System.out.println(pq.poll());
}
优先级队列是一种抽象数据类型,通常作为 Binary Heap 数据结构实现,而后者又(通常)用数组实现。 还有其他一些方法可以实现二叉堆,但是普通数组是最快、最简单、最好的方法。
数组如何表示二进制堆的示例,如下所示:
Queue order 未更改,在您的情况下;相反,您只是以错误的方式使用数据结构,仅通过传统的 for-each
/迭代方式对其进行迭代,就像在基本数组上进行迭代时一样,而不考虑您的优先级队列支持数组是未按其 ith 索引排序;相反,它将顶部元素保留在树的顶部(最小堆或最大堆的情况)并且您不能仅通过以传统方式对其进行迭代来获得 .poll()
效果。
这是因为 PriorityQueue 是最小堆的实现(默认在 Java 中),这意味着根元素将始终低于列表中的其他元素。
以你的问题为例:
- 插入10时,数组中索引1处的元素为10
- 当你插入 1 时,因为
1 < 10
位置 1 的元素现在是 1 而 10 它移动到索引 2 - 当你插入2时,因为
1 < 2
不需要移动元素,2被插入到索引3 - 当你插入 2 时,2 将小于 10,因为
10 > 2
需要一个移位,2 被插入到 2 并且 10 被写入索引 4
所有插入数组后看起来是这样的,同时查看下面的视频:
array: [NULL, 1, 2, 2, 10]
现在当你删除 2 时,10 需要移位,并且 10 被移回索引 2,并且数组的状态是 [NULL, 1, 10, 2]
这就是你在迭代时看到的输出.另外,检查在 PriorityQueue 中实现的 the following method,当您不提供 Comparator
.
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}