我和一个同学现在坐了几个小时来完成一项任务,没有从我们的程序中得到(小的?)错误。
任务是实现一个MinHeap,可以更新Elements并使用heapDown函数在MinHeap中对它们进行新排序。
现在,我们将其全部使用,但是堆数组的某些元素未放置到位,并且提取(最小元素)的列表未按她应有的顺序排序。
希望您能帮助我们。
import java.util.Random;
public class MinPQ2 {
private PQElement Elemente[];
private int maxsize;
private int currentsize;
public MinPQ2(int max) {
this.maxsize = max;
this.currentsize = 0;
Elemente = new PQElement[this.maxsize];
}
private void swap(int eins, int zwei) {//tauscht Elemente innerhalb des Arrays
PQElement tmp = Elemente[eins];
Elemente[eins] = Elemente[zwei];
Elemente[zwei] = tmp;
}
public PQElement getLeftChild(int position) {
return Elemente[position * 2 + 1];
}
public PQElement getRightChild(int position) {
return Elemente[position * 2 + 2];
}
public PQElement getQuestioner(int position){
return Elemente[position];
}
public PQElement getParent(int position) {
return Elemente[position / 2 - ((position > 0 && position % 2 == 0) ? 1 : 0)];
}
private void heapUp(int position) {
while (getParent(position).getPriority() > Elemente[position].getPriority()) {
int temppos = position / 2 - ((position % 2 == 0) ? 1 : 0);
swap(position, temppos);
position = temppos;
}
}
private void heapDown(int position) {
int tmp;
if (position * 2 + 2 < maxsize && getLeftChild(position) != null){
if (getRightChild(position) != null){
if (getLeftChild(position).getPriority() < getRightChild(position).getPriority()){
tmp = position *2+1;
swap(position,tmp);
position = tmp;
heapDown(position);
}
else {
tmp = position *2+2;
swap(position,tmp);
position = tmp;
heapDown(position);
}
}
else if (getLeftChild(position).getPriority() < getQuestioner(position).getPriority()){
tmp = position *2+1;
swap(position,tmp);
position = tmp;
heapDown(position);
}
}
}
public boolean insert(PQElement n) {
if (currentsize >= maxsize)
return false;
Elemente[currentsize] = n;
currentsize++;
if (currentsize > 1)
heapUp(currentsize - 1);
return true;
}
public boolean insert(String s, double d) {
return insert(new PQElement(s, d));
}
public PQElement extractElement() {
if(isEmpty())
return null;
PQElement result = Elemente[0];
swap(0, currentsize-1);
Elemente[currentsize - 1] = null;
heapDown(0);
currentsize--;
return result;
}
public String extractData() {
return extractElement().getData();
}
public boolean isEmpty() {
return currentsize == 0;
}
public void update(String s, double n) {
int position = currentsize - 1;
for (int i = 0; i <= currentsize; i++) {
if (i == currentsize)
return;
if (Elemente[i].getData().equals(s)) {
position = i;
break;
}
}
Elemente[position].setPriority(n);
heapUp(position);
heapDown(position);
}
}
public class PQElement {
private String data;
private double Priority;
public PQElement(String s, double d){
this.data = s;
this.Priority = d;
}
public String getData(){
return data;
}
public double getPriority(){
return Priority;
}
public void setPriority(double d){
Priority = d;
}
public void setData(String s){
data = s;
}
}
import java.util.Arrays;
import java.util.Random;
public class testclass {
public static void main(String[] args) {
Random zufall = new Random();
int max = 11;
MinPQ2 test = new MinPQ2(max);
for (int i = 0; i < max; i++) {
test.insert(i + " Element", zufall.nextDouble());
}
System.out.println(test(test, max));
System.out.println("_____________");
//test2(test,max);
System.out.println("_____________");
test3(test,max,zufall);
}
private static boolean test(MinPQ2 test, int max) {
for (int i = 1; i < max; i++) {
if (test.getParent(i).getPriority() < test.getQuestioner(i).getPriority()) {
System.out.println(test.getParent(i).getPriority() + " : " + test.getQuestioner(i).getPriority());
} else return false;
}
return true;
}
private static void test2(MinPQ2 test, int max) {
for (int i = 0; i < max; i++) {
System.out.println(test.extractElement().getPriority());
}
}
private static void test3(MinPQ2 test, int max, Random zufall){
for (int i = 1; i < max;i++){
if (i%2 == 0){
test.update(i + " Element", zufall.nextDouble());
}
}
test2(test,max);
}
}
这是我们的守则。
在testclass(第三个代码片段)中使用
test()
时,我们只显示了Heap,此时一切正常。但是现在在
test3()
中,我们更新了一些数据,并用heapDown()
(第一个代码段)对它们重新排序,并在屏幕上打印它们。现在我们看到提取的数据不是排序的。因此,错误可能出在heapDown()
或update()
中。但是我们尝试了很多,却没有找到解决方案:( 最佳答案
您的heapDown
方法中存在多个问题。我已添加评论。
private void heapDown(int position) {
int tmp;
// You need to check against `currentsize`, rather than maxsize.
if (position * 2 + 2 < maxsize && getLeftChild(position) != null){
// In this code, you always move the parent down, because
// you never compare the parent with its children.
if (getRightChild(position) != null){
if (getLeftChild(position).getPriority() < getRightChild(position).getPriority()){
tmp = position *2+1;
swap(position,tmp);
position = tmp;
heapDown(position);
}
else {
tmp = position *2+2;
swap(position,tmp);
position = tmp;
heapDown(position);
}
}
else if (getLeftChild(position).getPriority() < getQuesttioner(position).getPriority()){
tmp = position *2+1;
swap(position,tmp);
position = tmp;
heapDown(position);
}
}
}
您那里的代码过于复杂。您可以像这样简化它:
// first find the smallest child
leftChildIndex = position * 2 + 1;
if (leftChildIndex >= currentSize) return;
smallestChildIndex = leftChildIndex;
rightChildIndex = position * 2 + 2;
if (rightChildIndex < currentSize) {
if (getRightChild(position).getPriority() < getLeftChild(position).getPriority()) {
smallestChildIndex = rightChildIndex;
}
}
// if the parent is larger than the smallest child,
// then swap and repeat.
if (getQuestioner(smallestChildIndex).getPriority() < getQuestioner(position).getPriority()) {
swap(position, smallestChildIndex);
position = smallestChildIndex;
heapDown(position);
}