Вставка предмета в Max Heap

Question

Я не уверен, как вставить элемент в мою максимальную кучу, а затем накапливать так, чтобы свойство максимальной кучи сохранялось. Я выдал исключение, если heapArray заполнен, поэтому не могу вставить элемент.

Я не использую классы JCF или очередь с приоритетами для этой программы. Я также добавил свой метод deleteMax, который удаляет максимальное значение кучи и восстанавливает кучу, так что свойство max heap сохраняется.

public  class MaxIntHeap {
//my global var's
private int[] heapArray; // default size of 20 in constructor
private int lastOne; //equal to size of the array(heap)
private int size;
private int k;

public void heapInsert(int v) throws HeapException {
  if(lastOne == heapArray.length - 1 ){
  throw new HeapException("The value " + v + " cannot be inserted because the heap is FULL!");
  }
  else{ //This is where i am lost as to how i should insert
     lastOne++; //size of lastOne is increased.
}

Это мой метод removeMax.

public int  removeMax ()throws HeapException  { 
  if(size == 0){
     throw new HeapException("The Heap is empty, therefore the Max value of the heap cannot be       
     removed.");
  }
  else{
     int max = heapArray[0];
     heapArray[0] = heapArray[lastOne];
     lastOne--;
     k = 0;
     while(k > 0){
        int j = k / 2;
        if(heapArray[k] < heapArray[j]){
           swap(heapArray[k], heapArray[j]); //swap method...
           k = j;

        }
        else 
           break;
     }
     return max;
   }

  }

Любая помощь будет принята с благодарностью. Спасибо!

Answer 1

Ваш класс дизайн выглядит хорошо. В кучу:

leftChild = 2*parent +1
rightChild = 2*parent + 2
parent = (childindex-1)/2

Для максхепа,

1. Вставьте элемент, наконец. Тогда сравните это с его родителем.
2. Если родитель больше, чем эта последняя вставка, вы хороши.
3. Остальное поменять родителя и этого ребенка

4. Повторяйте, пока не дойдете до корня.

   MaxHeapImpl:

   public class MaxHeap {
   
   public int[] myHeap = new int[20];
   public int begin = 0;
   public int current = 0;
   
   public int getParent(int index){
       return (index - 1)/2;
   }
   
   public int getLeftChild(int index){
       return 2*index+1;
   }
   
   public int getRighChild(int index){
       return 2*index+2;
   }
   
   public void insert(int data) {
   
       myHeap[current] = data;
   
       int i = current;
       int tmp;
       int parent;
       while(i > 0){
           parent = getParent(i);
   
           System.out.println(" I value"+i+" parent"+parent+" data"+data);
           if(myHeap[parent] < myHeap[i]){
               tmp = myHeap[parent];
               myHeap[parent] = myHeap[i];
               myHeap[i] = tmp;
           } else{
               break;
           }
   
           i = parent;
   
       }
       current++;
   }
   

   }

TestClass:

    public class MaxHeapTest {

    @Test
    public void test() {
        MaxHeap myHeap = new MaxHeap();

        myHeap.insert(40);
        myHeap.insert(20);
        myHeap.insert(10);
        myHeap.insert(25);
        myHeap.insert(30);
        myHeap.insert(100);

        for(int i = 0; i < myHeap.current;i++){
            System.out.println(" "+myHeap.myHeap[i]);
        }
    }

}

Answer 2

Чтобы исправить ответ выше, ток не равен 0, а равен размеру кучи (со значением).

int getParent(int index){                                 
    return (index - 1)/2;                                 
}                                 
                                  
void insertHeap(Array tab){                               
    int current = tab.size() -1;                                  
    int i = current;                                  
    int tmp;                                  
    int parent;                               
    while(i > 0) {                                
        parent = getParent(i);                                
        if(tab[parent] < tab[i]) {                                
            tmp = tab[parent];                                
            tab[parent] = tab[i];                                 
            tab[i] = tmp;                                 
        } else break;                                 
        i = parent;                               
    }                                 
    current++;                                
}