代码之家 › 专栏 › 技术社区 › Pasha

在Java PriorityQueue中,为什么队列[n]的子级是队列[2n+1]和队列[2(n+1)]?

priority-queue java

Pasha · 技术社区 · 5 年前

Java中的最小堆实现由PriorityQueue表示,PriorityQueue由 transient Object[] queue;

其javadoc中的引用是

优先级队列表示为一个平衡的二进制堆:两个子堆队列[n]的类型包括队列[2n+1]和队列[2(n+1)]。

0 回复 | 直到 5 年前

Brian_E 5 年前

正如caco3在命令中提到的,如果优先级队列中的元素存储在一个数组中,那么该优先级队列数据结构的设计者可以决定将数组中的第一项存储在位置0或位置1。

将第一项置于位置0意味着孩子们处于位置2N+1和2N+2。当第一项存储在位置1时,子项位于位置2N和2N+1。

任何一种选择都可能导致正确的实现。从0开始可以节省一点空间。但有些人觉得从1开始,数学和代码就更优雅了。

推荐文章

user29759326 · 如何返回递归函数中的最后一个值?

1 年前

malife89 · 将java中的字符串读取为正确的日期格式

1 年前

Tim · 在java中,有没有更快的方法将字节数组写入文件?

1 年前

pebble unit · 如何检查以前缀开头、以后缀结尾的属性(不是属性值)

1 年前

Nuñito Calzada · Spring Boot with JWT:访问此资源需要完全身份验证

1 年前

rudraraj · java中未声明最终变量

1 年前

Bala Ji · 以下BFS的实施效率如何?

1 年前

MineRickStar · 如何在Java中从Windows获取当前选定的应用程序

1 年前

user2649681 · 实时生成音频以写入“SourceDataLine”`

1 年前

davidalayachew · 为什么我的文件有竞争条件,即使我使用了StandardOpenOption。同步?

1 年前

在Java PriorityQueue中,为什么队列[n]的子级是队列[2*n+1]和队列[2*(n+1)]?