java - 最大堆插入和排序 Java
问题描述
我正在尝试构建一个最大堆,并且随着每个新值的插入,该值会向上或向下移动到正确的位置,我还没有实现向下移动功能,所以到目前为止我正在使用一个应该只要求程序向上移动。测试数据按以下顺序输入:
[16、10、14、9、7、1、4、2、8、3]
我在主类中使用以下代码在堆中插入值:
package com.company;
public class Main {
public static void main(String[] args) {
BinaryHeap bh = new BinaryHeap();
bh.insert(16);
bh.insert(10);
bh.insert(14);
bh.insert(9);
bh.insert(7);
bh.insert(1);
bh.insert(4);
bh.insert(2);
bh.insert(8);
bh.insert(3);
bh.printHeap();
}
}
下一段代码是插入和移位发生的地方:
package com.company;
public class BinaryHeap {
private int[] Heap;
private int size;
private int maxsize;
public BinaryHeap(){
this.maxsize = 10;
this.size = 0;
Heap = new int[this.maxsize + 1];
}
public int Parent(int i){
return (i)/2;
}
public int LeftChild(int i){
return (2*i);
}
public int RightChild(int i){
return ((2*1)+1);
}
public void insert(int value) {
if(size <= Heap.length) {
size++;
Heap[size] = value;
siftUp(size);
}
}
private void siftUp(int i) {
int parentIndex;
int tmp;
if (i != 0) {
parentIndex = Parent(i);
if (Heap[parentIndex] < Heap[i]) {
tmp = Heap[parentIndex];
Heap[parentIndex] = Heap[i];
Heap[i] = tmp;
siftUp(parentIndex);
}
}
}
public void printHeap()
{
for (int i = 1; i < maxsize; i++) {
System.out.print(" PARENT : " + Heap[Parent(i)]
+ " LEFT CHILD : " + Heap[LeftChild(i)]
+ " RIGHT CHILD :" + Heap[RightChild(i)]);
System.out.println();
}
}
}
移位功能是 siftUp() 我认为这是问题所在。当程序使用这些输出运行时:
PARENT : 16 LEFT CHILD : 9 RIGHT CHILD :10
PARENT : 14 LEFT CHILD : 8 RIGHT CHILD :10
PARENT : 14 LEFT CHILD : 1 RIGHT CHILD :10
PARENT : 9 LEFT CHILD : 0 RIGHT CHILD :10
PARENT : 9 LEFT CHILD : 3 RIGHT CHILD :10
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 12 out of bounds for length 11
at com.company.BinaryHeap.printHeap(BinaryHeap.java:61)
at com.company.Main.main(Main.java:20)
但这是不正确的,因为 1)最后的索引超出范围异常来自 printHeap() 函数和 2)每个父节点的子节点不在正确的位置,因为根节点应该是 16以 14 和 10 作为孩子,当它打印出堆的值时,它打印出 0 但是 0 永远不会插入到堆中。我已经尝试过自己进行一些调试,但没有太大成功,因此欢迎提供任何帮助。
解决方案
private void siftUp(int i) {
int parentIndex;
int tmp;
if (i != 0) { // error is this if statement
parentIndex = Parent(i);
if (Heap[parentIndex] < Heap[i]) {
tmp = Heap[parentIndex];
Heap[parentIndex] = Heap[i];
Heap[i] = tmp;
siftUp(parentIndex);
}
}
}
导致您的堆不显示正确数字的错误在 siftUp 中,即 if 语句。
当您插入 16 时,Heap[1]
变为 16。然后,它调用siftUp(1)
. 在 siftUp 内部,1 != 0,因此执行 if 语句。parentIndex 变为 1/2 = 0,问题就来了。默认情况下,Heap[0] = 0 小于 Heap[1] = 16。因此,它交换值 16 和 0,将 16 移动到索引 0,这不是您提到的头部。这只是错误的开始,当您插入越来越多的数字时,它们会变得无处不在。
由于您的堆根位于索引 1。您应该只筛选到没有父级的索引 1。将 if 语句更改为if(i > 1)
并修改 printHeap() 后,我得到了这个输出,我认为这是正确的。您还应该在堆中的当前索引处打印当前值。
PARENT: 0 CURRENT: 16 LEFT CHILD : 10 RIGHT CHILD : 14
PARENT: 16 CURRENT: 10 LEFT CHILD : 9 RIGHT CHILD : 7
PARENT: 16 CURRENT: 14 LEFT CHILD : 1 RIGHT CHILD : 4
PARENT: 10 CURRENT: 9 LEFT CHILD : 2 RIGHT CHILD : 8
PARENT: 10 CURRENT: 7 LEFT CHILD : 3
PARENT: 14 CURRENT: 1
PARENT: 14 CURRENT: 4
PARENT: 9 CURRENT: 2
PARENT: 9 CURRENT: 8
public void printHeap(){
for (int i = 1; i < maxsize; i++) {
System.out.print(" PARENT: " + Heap[Parent(i)]);
System.out.print(" CURRENT: "+ Heap[i]);
if(LeftChild(i) <= 10){
System.out.print(" LEFT CHILD " + ": " + Heap[LeftChild(i)]);
}
if(RightChild(i) <= 10){
System.out.print(" RIGHT CHILD "+ ": "+ Heap[RightChild(i)]);
}
System.out.println();
}
}
推荐阅读
- python-2.7 - Jinja2 中的宏不返回列表?
- spring-boot - 通过 HTTPS 公开 Google 计算引擎或 Kubernetes
- ruby - 制作一个根据可变长度插入空格的函数
- snowflake-cloud-data-platform - 如何在雪花中获取完整的功能表并测试它是否正常工作
- woocommerce - coupon_lines 在 woocommerce REST API 中不起作用?
- python - Django Rest Framework 如何禁止用户更改用户名?
- c++ - 对使用 'typedef' 声明的函数使用 'override'
- java - 如何使用 MockIntegrationContext.substituteMessageHandlerFor 模拟 WebFluxRequestExecutingMessageHandler
- javascript - 每当我尝试从中调用方法时 Service 未定义
- php - 在 PHP 中获取用户的语言