Блог

Я пытаюсь написать функцию добавления для минимальной кучи на Java, но, похоже, я не могу написать ту, которая работает должным образом. Я уже пробовал два решения для метода add, но ни одно из них, похоже, не работает. Я пробовал использовать int, чтобы сохранить предыдущую позицию, а затем снова вставить ее в кучу, но это не дает никаких результатов. Любая помощь будет очень признательна.

 public class ClsPQHeap {
    private int back;
    private int heap[];

public ClsPQHeap (int amount){
    heap = new int[amount];
    back = 0;
}
public boolean isEmpty(){
    if (back == 0){
      return true;  
    } else {
      return false;  
    }
}
public boolean isFull(){
    if (heap.length == back){
        return true;
    } else {
        return false;
    }
}
// this is the method that needs help 
public void add(int x){
    if (isEmpty()) {
        heap[back] = x;
    } else if (isFull()){
      System.out.println("Did not add "   x   " array is full");
   } else {
        heap[back   1] = x;
        for (int i = heap.length; i <= back; i--){
            if (heap[i] > heap[i-1]){
                int temp = heap[i];
                heap[i] = heap[i-1];
                heap[i-1] = temp;
            } else if (heap[i] < heap[i -1]){
                int temp = heap[i];
            }
        }
        /*do {
            if (heap[back] > heap[back 1]){
                int temp = heap[back];
                heap[back] = heap[back   1];
                heap[back   1] = temp;
            } else if (heap[back] < heap[back 1]){
            
            }
        } while (heap[0] > heap[back]); */
        back  = 1;    
    } 
}
public void print(){
  int count = 1;
  for(int i = 0; i<back; i  ){
     System.out.println(count   "."   heap[i]);
     count  = 1;
  }
}
public static void main(String[] args) {
    
    int myArray[] = {15, 5, 8, 4, 9, 22, 17, 2, 14, 1};
    ClsPQHeap heap = new ClsPQHeap(myArray.length);
    for(int i = 0; i<myArray.length; i  ){
        heap.add(myArray[i]);
        heap.print();
        System.out.println("");
    }
}
}
 

Я немного продвинулся с тех пор, как опубликовал это в функции добавления. Теперь я могу распечатать некоторые из них, но значения печатаются неправильно или добавляются неправильно. Вот где я в настоящее время нахожусь:

 public void add(int x){
    back = back 1;
    if (isEmpty()) {
        heap[back] = x;
    } else if (isFull()){
      System.out.println("Did not add "   x   " array is full");
      back = back-1;
   } 
    heap[back   1] = x;
    for (int i = 1; i<= back 1; i  ){
        if (heap[i-1] <= heap[(i-1)/2]){
            int holder;
            holder = heap[i-1];
            heap[i-1] = heap[(i-1)/2];
            heap[(i-1)/2] = holder; 
            }
        }
}
 

Некоторые вопросы:

• for Условие неверно в первой версии: по мере уменьшения i условие должно быть против минимального предела, например i >= 0 . Во второй версии это цикл увеличения, который решает проблему, за исключением того, что алгоритму вставки действительно нужен цикл уменьшения, представляющий собой переход от нижней части дерева к корню.
• В первой версии вы не увеличиваете back размер, когда список пуст. Это решается во второй версии. Однако во второй версии вы не заполняете запись с индексом 0.
• В первой версии связь между дочерним и родительским узлами не рассчитывается в терминах индексов. Это несколько лучше описано во второй версии-с использованием деления на 2, — но это все еще не совсем правильно.

Вот как это можно было бы сделать. Обратите внимание, что нет необходимости по-другому относиться к пустому списку. Кроме того, нет необходимости менять местами в каждой итерации. Просто сдвиньте значения вниз, оставив пробел для значения x , но назначьте значение только x тогда, когда будет определен правильный целевой индекс. Это экономит некоторые ненужные задания на этом пути.

     public void add(int x){
        if (isFull()){
            System.out.println("Did not add "   x   " array is full");
        } else {
            int child = back;
            int parent = (child - 1) / 2;
            while (child > 0 amp;amp; heap[parent] > x) {
                heap[child] = heap[parent];
                child = parent;
                parent = (child - 1) / 2;
            }
            heap[child] = x;
            back  ;
        }
    }