Я и сокурсник часами сидим за заданием и не получаем (маленькую?) Ошибку из нашей программы.
Задача состоит в том, чтобы реализовать MinHeap с возможностью обновления Elementsи отсортировать их в MinHeap с помощью функции heapDown. Теперь мы приводим все это в действие, но некоторые элементы нашего массива кучи не находятся на месте, и список после нашего экстракта (самого маленького элемента) не сортируется должным образом. Надеюсь, вы можете помочь нам.
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);
}
}
Это наш Кодекс. С test() в тестовом классе (третий codenippet) мы просто показываем кучу, и на этом месте все работает нормально. Но теперь в test3() мы обновляем некоторые данные, переупорядочиваем их с помощью heapDown() (первый фрагмент кода) и выводим их на экран. Теперь мы видим, что данные извлечения не в сортировке. Так что ошибка может быть в heapDown() или update(). Но мы очень стараемся и не находим решение: (