- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我有一个随机生成的测试程序,数据是随机生成的,然后将它们传递给类 Sorter 的类构造函数。然后Sorter会对数据进行排序,通过一个方法传回给main函数。我还实现了其他几种排序方法作为 Sorter 类的子类,它们工作得很好。所以我认为我的 Sorter 类没有问题。下面是我的测试程序在使用堆排序时的输出。
数据:
48 96 71 81 78 72 93 52 67 70
排序数据:
48 71 81 78 72 67 52 93 70 96
如您所见,经过以下代码后数据未排序。下面是代码。
public class HeapSort extends Sorter{
private int[] heap;
private int size;
public HeapSort(int[] data){
super(data);
}
public void sort(){
constructHeap();
for(int i = size - 1; i >= 0; i--){
numbers[i] = extractMax();
}
}
public void constructHeap(){
size = numbers.length;
heap = new int[size];
for(int j = 0; j < size; j++) heap[j] = numbers[j];
for(int i = size/2 - 1; i >= 0; i--){
fixHeap(i, heap[i]);
}
}
public int extractMax(){
int max = heap[0];
fixHeap(0, heap[--size]);
return max;
}
public void fixHeap(int pos, int key){
if(left(pos) > size) heap[pos] = key; // if current position is leaf
else{
int largest = pos;
int r = right(pos);
int l = left(pos);
if(r < size && heap[largest] < heap[r]) largest = r;
if(l < size && heap[largest] < heap[l]) largest = l;
if(largest == pos) heap[pos] = key;
else{
heap[pos] = heap[largest];
fixHeap(largest, key);
}
}
}
public int left(int i){return 2*i+1;}
public int right(int i){return 2*i+2;}
}
编辑:下面是调试后的代码。希望有人会觉得它有用。
public class HeapSort extends Sorter{
private int[] heap;
private int size;
public HeapSort(int[] data){
super(data);
}
public void sort(){
constructHeap();
for(int i = size - 1; i >= 0; i--){
numbers[i] = extractMax();
}
}
public void constructHeap(){
size = numbers.length;
heap = new int[size];
for(int j = 0; j < size; j++) heap[j] = numbers[j];
for(int i = size/2 - 1; i >= 0; i--){
fixHeap(i);
}
}
public int extractMax(){
int max = heap[0];
heap[0] = heap[--size];
fixHeap(0);
return max;
}
public void fixHeap(int pos){
if(left(pos) < size){ // if current position is not leaf
int largest = pos;
int r = right(pos);
int l = left(pos);
if(r < size && heap[largest] < heap[r]) largest = r;
if(l < size && heap[largest] < heap[l]) largest = l;
if(largest != pos){
exchange(pos, largest);
fixHeap(largest);
}
}
}
public int left(int i){return 2*i+1;}
public int right(int i){return 2*i+2;}
public void exchange(int a, int b){
int temp = heap[a];
heap[a] = heap[b];
heap[b] = temp;
}
}
最佳答案
我假设您有一个调试器,并且知道如何使用它。
在我看来,调试复杂代码的最佳方式就是我所说的“分而治之调试”。伪代码:
void debug(Time beforeTheBug, Time afterTheBug) {
do {
Time pivot = between(beforeTheBug, afterTheBug);
if (stateIsAsExceptedAt(pivot)) {
afterTheBug = pivot;
} else {
beforetheBug = pivot;
}
} while (amountOfCodeExecutedBetween(beforeTheBug, afterTheBug) is not trivial);
}
在你的例子中,我的第一个检查是输出。确实没有排序,所以bug在这个类。
我的下一个检查是在 constructHeap 之后是否满足堆不变量。当时heap
为[96, 48, 93, 81, 78, 72, 71, 52, 67, 70],所以不满足堆不变量(48不大于78) ,并且在构建堆期间出现错误。
查看 constructHeap() 没有发现有用的断点,因为第一个循环非常简单,而且不太可能出错,而第二个循环(调用 fixHeap)包含所有复杂性。
循环的第一次迭代没有发现任何改变,这是正确的,因为子树已经满足堆不变量。第二次迭代相同。
第三次迭代正确识别右 child 大于根,并交换两者。
第四次迭代发现没有任何变化,这是正确的。
所以它是包含问题的循环的最后一次迭代。两个 child 都比 parent 大。 fixHeap 正确地将较大的 child 移动到根中,并递归调用自身。该调用发现堆不变量得到满足,并返回。但返回后不满足不变量。
所以问题出在从检测堆不变性到返回的某个地方。检测检查:
if (r < size && heap[largest] < heap[r])
largest = r;
if (l < size && heap[largest] < heap[l])
largest = l;
其中 heap
是 [96, 96, 93, 81, 78, 72, 71, 52, 67, 70]。是的,96 大于 81 和 78。但实际上,heap[pos] == key
不应该吗?啊,这就是下一条语句的作用...
换句话说,我们在完成上一次更新之前检查堆不变量,然后完成该更新,这在这种情况下破坏了不变量......
关于java - 调试 HeapSort Java 代码,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19332634/
我已经看了好几个小时了,还是想不通。如果 heapify 函数中的比较更改为大于,则输出按应有的顺序递增。我希望我的列表按降序排序,但它没有使用以下代码给出正确的输出: #include #incl
我是 C++/算法的新手,我不太确定我的 heapSort 函数有什么问题。给定数字(6、2、9、1、5),我输出了以下不正确的数字: 9 4197040 2 4196422 6 感谢您的关注。 #i
我卡在 heapSort 上了。我有一些代码,但我认为它是错误的,因为我很难编译它。有什么建议么?堆排序应该很容易实现,但我有一堆语法错误。这是我的代码: /* Framework for Heap
考虑一个已经按降序排列的数组 A[n]。堆已经建立。现在考虑我们将 A[1](数组索引从 1 开始)与 A[heap.size] 交换的循环。这是伪代码: Build-Max-Heap(A) //Al
我正在研究算法,特别是堆排序。根据我的理解,heapsort 算法涉及通过首先将列表转换为最大堆来准备列表。 转动我的 [2, 8, 5, 3, 9, 1] 进入 [9, 8, 5, 3, 2, 1]
我在 http://students.ceid.upatras.gr/~lebenteas/Heapsort-using-Multiple-Heaps-final.pdf 找到了使用多个堆的 Heap
传统的Heapsort 算法在每次heapification 后将堆的最后一个元素与当前堆的根交换,然后再次继续该过程。但是,我注意到这是不必要的。 在子数组的堆化之后,当节点包含最高值(如果它是ma
任务是为数组中未知类型的元素编写堆排序(仅使用 C 代码),但我的代码不起作用。对于以下数字输出是 '-100 7 -4 0 33 -3 67 1 5 44' 我也尝试将相同的代码仅用于 int 输入
代码如下: import java.util.Arrays; public class HeapSort { pub
有人可以描述一种算法,该算法在最小堆的数组实现中找到所有小于 x 的键。 我希望运行时间至少为 O(k),其中 k 是报告的键数。 我已经为此挠头一段时间了。 最佳答案 树最小堆有一个简单的递归算法:
出于某种原因,我的 Heapsort 无法正常工作。使用以下测试程序: int main() { AddArrayElement(10); AddArrayElement(110);
我正在尝试使用最小堆实现堆排序。输入是正整数数组,数组的零索引存储大小。谁能发现我的错误?这里使用的语言是 C#。该算法有时可以正常工作,但对于更大的数组,根不是数组中的最小值。 static
我正在尝试用 java 编写一个堆排序方法,但它并没有完全按照我想要的方式工作: public class HeapSort { private static int n; priva
我今天写了两个不同的堆排序实现,都给了我相同的结果: Object i: 18 Object i: 11 Object i: 10 Object i: 9 Object i: 8 Object i:
我正在为软件开发人员面试做准备,并且一直在研究算法问题。我的书展示了一种 Heapsort 算法,它可以按升序对无序数组进行排序。我正在尝试修改它,以便它可以使用最小堆进行排序。但是当我按照代码中的逻
我必须在 C# 中检查 HeapSort 算法时间,我的问题是我知道我必须使用 System.Timers,因为我不知道如何测量算法时间。我必须检查表的算法时间包含 1000、10 000、100 0
我读到 C++ 对其内置的 std::sort 使用 introsort(内省(introspection)排序),它从快速排序开始,并在达到深度限制时切换到堆排序。 我还读到深度限制应该是 2*lo
对于类(class),我必须实现 BST 或 heapSort。我做了 BST,但认为也知道这一点会很好,但现在我被困住了。这是我第一次使用堆(并且真正使用泛型编码/实现 Comparable,所以我
我有一个随机生成的测试程序,数据是随机生成的,然后将它们传递给类 Sorter 的类构造函数。然后Sorter会对数据进行排序,通过一个方法传回给main函数。我还实现了其他几种排序方法作为 Sort
假设我有一个 vector 要排序: std::vector v{9, 8, 0, 2, 7, 3, 2, 1} 假设我想从第三个元素(索引 2)开始排序直到结束,所以我有一个迭代器指向 0 表示开始
我是一名优秀的程序员,十分优秀!