Вставка элемента в максимальную кучу

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

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

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;
   }

  }

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


java insert heapsort max-heap
person evilA    schedule 29.09.2014    source источник

Ответы (2)


arrow_upward
1
arrow_downward

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

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++;
}

    }

ТестКласс:

    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]);
        }
    }

}
person user892871    schedule 29.09.2014

arrow_upward
0
arrow_downward

чтобы исправить ответ выше, ток равен не 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++;                                
}
person Yolan Maldonado    schedule 24.10.2020