小根堆调整后打印的值不正确。

huangapple go评论74阅读模式
英文:

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&lt;Integer&gt; heap, int value) {
		if(heap.isEmpty()) {
			heap.add(value);
		}
		else {
			heap.add(value);
			for(int index = heap.size() / 2 - 1;index &gt;= 0;index--) {
				minHeapify(heap, index);
			}
		}
	}
	
	public void minHeapify(List&lt;Integer&gt; heap, int index) {
		int smallest = index;
		int leftChildIndex = 2 * index + 1;
		int rightChildIndex = 2 * index + 2;
		
		if(leftChildIndex &lt; heap.size() &amp;&amp; heap.get(leftChildIndex) &lt; heap.get(smallest)) {
			smallest = leftChildIndex;
		}
		if(rightChildIndex &lt; heap.size() &amp;&amp; heap.get(rightChildIndex) &lt; 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&lt;Integer&gt; input2 = new ArrayList&lt;Integer&gt;();
		
		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.

https://www.geeksforgeeks.org/heap-data-structure/

huangapple
  • 本文由 发表于 2020年8月18日 10:58:37
  • 转载请务必保留本文链接:https://go.coder-hub.com/63461247.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定