HeapSort理论？
我不是使用HeapSort对已填充的数组进行排序，而是在填充数组时使用HeapSort。
对于最小值位于顶部的堆，我的理解是，当您向堆中插入新值时，您会检查父节点，看新的子节点是否更大。如果是，你什么都不做，如果不是，你检查并根据需要在树上交换？
这是不是因为我的实现根本不起作用：
public class HeapSort{
static int[] numbers = new int[] { 0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
static int[] array = new int[16];
public static void main(String[] args) {
for (int i = 1; i < 15; i++) {
array[i] = numbers[i];
if (i > 1)
sort(i);
}
for (int i = 1; i < 15; i++) {
System.out.println(array[i]);
}
}
public static void sort(int i) {
int parentLocation = i / 2;
int childLocation = i;
int parentValue = array[parentLocation];
int childValue = array[childLocation];
if(parentValue > childValue){
array[parentLocation] = childValue;
array[childLocation] = parentValue;
}
if(parentLocation != 1){
sort(parentLocation);
}
}
}提亚
如果它有任何帮助，这是当我向后给它1-15的时候的输出：
2
6
3
9
7
5
4
15
12
13
8
14
10
11但是你们看起来和我一样被难住了！
回答 3
Stack Overflow用户
发布于 2011-12-11 07:35:35
看起来你没有对整个数组进行排序。假设您有10个正确排序的字段，并插入number。所以你有
-，1，2，3，4，5，6，7，8，9，11和插入10 (应该是倒数第二，这是因为你从来没有把任何东西放在那里)
现在你的算法比较了parentLocation 5 ( 11 /2)和childLocation 11，对吗？好吧，5比11小，所以不交换任何东西。然后继续使用input 5进行排序。
这一次你比较parentLocation 2 (5/2)和childLocation 5.2。2小于5，仍然没有变化。
直到完成。但是你从来没有测试过10和11的顺序是否正确，你是从一半开始的。
最简单的修复方法是将您的两次迭代改为
for (int i = 1; i < numbers.length; i++) {...}
...
for (int i = 1; i < array.length; i++) {...}因为您缺少当前代码中的结尾位置。
然后将sort()中的第一行更改为
int parentLocation = i - 1;这样，您的递归检查将检查整个数组。但这是常规排序，不是heapy :)
添加了完整的新解决方案:)我确信这不是最优解决方案，但它很容易遵循。我已经用ArrayList替换了目标堆，以便能够轻松地缩小它。
package se.wederbrand.stackoverflow;
import java.util.ArrayList;
public class HeapSort {
static int[] numbers = new int[]{0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
static ArrayList<Integer> heap = new ArrayList<Integer>();
public static void main(String[] args) {
// add 0 at the first position
heap.add(0);
for (int i = 1; i < numbers.length; i++) {
heap.add(numbers[i]);
if (i > 1) {
reheapifyBottomUp(i);
}
}
while (heap.size() > 1) {
System.out.println(removeFirstFromHeap());
}
}
private static int removeFirstFromHeap() {
// the value at index 1 should be returned
int returnValue = heap.get(1);
// the last node is replacing the removed one
if (heap.size() > 2) {
heap.set(1, heap.remove(heap.size() - 1));
reheapifyTopDown(1);
}
else {
heap.remove(1);
}
return returnValue;
}
public static void reheapifyBottomUp(int childLocation) {
int parentLocation = childLocation / 2;
int parentValue = heap.get(parentLocation);
int childValue = heap.get(childLocation);
if (parentValue > childValue) {
heap.set(parentLocation, childValue);
heap.set(childLocation, parentValue);
}
if (parentLocation != 1) {
reheapifyBottomUp(parentLocation);
}
}
public static void reheapifyTopDown(int parentLocation) {
int childLocation1 = parentLocation * 2;
int childLocation2 = childLocation1 + 1;
int parentValue = heap.get(parentLocation);
int childValue1 = Integer.MAX_VALUE;
if (heap.size() > childLocation1) {
childValue1 = heap.get(childLocation1);
}
int childValue2 = Integer.MAX_VALUE;
if (heap.size() > childLocation2) {
childValue2 = heap.get(childLocation2);
}
if (childValue1 <= childValue2 && parentValue > childValue1) {
// swap them and continue down
heap.set(parentLocation, childValue1);
heap.set(childLocation1, parentValue);
reheapifyTopDown(childLocation1);
}
else if (childValue2 < childValue1 && parentValue > childValue2) {
// swap them and continue down
heap.set(parentLocation, childValue2);
heap.set(childLocation2, parentValue);
reheapifyTopDown(childLocation2);
}
}
}Stack Overflow用户
发布于 2011-12-11 07:49:49
这里所做的全部工作就是将一堆数字添加到堆中(乍一看，这看起来是正确的)。数组包含堆中的值，而不是排序列表中的值。要获得排序后的列表，在堆排序中，您需要不断弹出最小的元素并重新堆积。您错过了这一步；您只是在开始该过程之前打印出最终的堆。
Stack Overflow用户
发布于 2011-12-11 14:28:06
您的排序方法应该重命名为heapify()。您当前的sort()方法只是重新排列堆。
最小/最大堆从不排序，因此您永远不能像遍历二进制搜索树那样遍历它。您必须实现类似removeMin()的东西，它将从堆中删除最顶层的元素，并对剩余的堆执行排序。
https://stackoverflow.com/questions/8460567
复制相似问题
腾讯云开发者
