英文:
MinHeapify printing incorrect value
问题
以下是您提供的代码的翻译:
import java.util.List;
import java.util.ArrayList;
public class Heap {
public void insert2(List<Integer> heap, int value) {
if(heap.isEmpty()) {
heap.add(value);
}
else {
heap.add(value);
for(int index = heap.size() / 2 - 1; index >= 0; index--) {
minHeapify(heap, index);
}
}
}
public void minHeapify(List<Integer> heap, int index) {
int smallest = index;
int leftChildIndex = 2 * index + 1;
int rightChildIndex = 2 * index + 2;
if(leftChildIndex < heap.size() && heap.get(leftChildIndex) < heap.get(smallest)) {
smallest = leftChildIndex;
}
if(rightChildIndex < heap.size() && heap.get(rightChildIndex) < heap.get(smallest)) {
smallest = rightChildIndex;
}
if(smallest != index) {
int temp = heap.get(smallest);
heap.set(smallest, heap.get(index));
heap.set(index, temp);
minHeapify(heap, smallest);
}
}
public static void main(String[] args) {
List<Integer> input2 = new ArrayList<Integer>();
Heap heap2 = new Heap();
heap2.insert2(input2, 3);
heap2.insert2(input2, 4);
heap2.insert2(input2, 48);
heap2.insert2(input2, 9);
heap2.insert2(input2, 5);
heap2.insert2(input2, 2);
System.out.println(input2);
}
}
输出为 [2, 4, 3, 9, 5, 48]
最小堆的输出应该始终是有序的。我的假设是正确的吗?输出是否应该为 [2, 3, 4, 5, 9, 48]
?
英文:
I am trying to visualize why my minHeapify
is isn't sorting correctly. Here is my code:
import java.util.List;
import java.util.ArrayList;
public class Heap {
public void insert2(List<Integer> heap, int value) {
if(heap.isEmpty()) {
heap.add(value);
}
else {
heap.add(value);
for(int index = heap.size() / 2 - 1;index >= 0;index--) {
minHeapify(heap, index);
}
}
}
public void minHeapify(List<Integer> heap, int index) {
int smallest = index;
int leftChildIndex = 2 * index + 1;
int rightChildIndex = 2 * index + 2;
if(leftChildIndex < heap.size() && heap.get(leftChildIndex) < heap.get(smallest)) {
smallest = leftChildIndex;
}
if(rightChildIndex < heap.size() && heap.get(rightChildIndex) < heap.get(smallest)) {
smallest = rightChildIndex;
}
if(smallest != index) {
int temp = heap.get(smallest);
heap.set(smallest, heap.get(index));
heap.set(index, temp);
minHeapify(heap, smallest);
}
}
public static void main(String[] args) {
List<Integer> input2 = new ArrayList<Integer>();
Heap heap2 = new Heap();
heap2.insert2(input2, 3);
heap2.insert2(input2, 4);
heap2.insert2(input2, 48);
heap2.insert2(input2, 9);
heap2.insert2(input2, 5);
heap2.insert2(input2, 2);
System.out.println(input2);
}
}
The output is [2, 4, 3, 9, 5, 48]
The output for min heap should always be sorted. Am I correct with this assumption and should it be [2, 3, 4, 5, 9, 48]
?
答案1
得分: 0
你的实现是正确的,经过你以下的插入步骤后,结果确实是 [2, 4, 3, 9, 5, 48]
。
最小堆的输出应该始终是有序的
但是你对于 MinHeap
有一个小错误的理解,即每个节点都比它的左右子节点小。但是右子节点可以比它的兄弟节点大或小,只要它比父节点大即可。
因此,你的堆的表示形式无法以正确的顺序排序。
链接:https://www.geeksforgeeks.org/heap-data-structure/
英文:
Your implementation is correct, and the result after your following insert steps is truely [2, 4, 3, 9, 5, 48]
.
> The output for min heap should be always sorted
But you are getting a little wrong idea about MinHeap
, which is every node is smaller than it left and right children node. BUT the right child node can be greater, smaller than it sibling as long as greater than its parent.
So the represented List
of your heap can't be sort in correct order.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论