Max Heap funktioniert nicht wie erwartet

Question

Mein Java-Code für Max Heap funktioniert nicht wie erwartet. Außerdem gibt es nicht 90 als Max zurück, wenn ich vom Heap entferne.

/** 
* Created by mona on 5/25/16. 
*/ 
public class Heap { 
    private int[] heap; 
    private int size; 
    private int maxSize; 


    public Heap(int maxSize) { 
     this.maxSize=maxSize; 
     this.size=0; 
     heap=new int[this.maxSize+1]; 
    } 

    private int parent(int pos) { 
     return pos/2; 
    } 

    private int leftChild(int pos) { 
     return pos*2; 
    } 

    private int rightChild(int pos) { 
     return pos*2 +1; 
    } 

    private boolean isLeaf(int pos) { 
     if (pos>=size/2 && pos<=size) { 
      return true; 
     } 
     return false; 
    } 

    private void swap(int pos1, int pos2) { 
     int tmp=heap[pos1]; 
     heap[pos1]=heap[pos2]; 
     heap[pos2]=tmp; 
    } 


    private void maxHeapify(int pos) { 
     if (!isLeaf(pos)){ 
      if ((heap[pos] < heap[leftChild(pos)]) || 
       (heap[pos] < heap[rightChild(pos)])) { 
      if (heap[leftChild(pos)] > heap[rightChild(pos)]) { 
       swap(pos , leftChild(pos)); 
       maxHeapify(leftChild(pos)); 
      } 
      else { 
       swap(pos , rightChild(pos)); 
       maxHeapify(rightChild(pos)); 
      } 

      } 

     } 
    } 

    public void maxHeap() { 
     for (int i=(size/2) ; i>=1 ; i--) { 
      maxHeapify(i); 
     } 
    } 

    public void insert(int n) { 
     heap[++size] = n; 
     int tmpLocation = size; 
     while (heap[tmpLocation] > heap[parent(tmpLocation)]){ 
      swap(tmpLocation , parent(tmpLocation)); 
      tmpLocation=parent(tmpLocation); 
     } 


    } 

    public int remove() { 
     int removed = heap[1]; 
     heap[1] = heap[size-1]; 
     maxHeapify(1); 
     return removed; 
    } 

    public void print() { 
     for (int i=1 ; i<=(size/2) ; i++) { 
      System.out.println("current node is: "+heap[i]+" its left child is " + 
        heap[i*2]+" its right child is "+heap[i*2 +1]); 
     } 

    } 

    public static void main(String[] args) { 
     Heap heap = new Heap(9); 
     heap.insert(8); 
     heap.insert(18); 
     heap.insert(28); 
     heap.insert(9); 
     heap.insert(12); 
     heap.insert(90); 
     heap.insert(1); 
     heap.insert(87); 
     heap.maxHeap(); 

     heap.print(); 
     System.out.println("Max is: "+heap.remove()); 

    } 


} 

Hier ist der Ausgang:

current node is: 90 its left child is 90 its right child is 87 
current node is: 87 its left child is 28 its right child is 18 
current node is: 28 its left child is 12 its right child is 9 
current node is: 18 its left child is 8 its right child is 1 
current node is: 12 its left child is 0 its right child is 0 
Max is: 87 

Process finished with exit code 0 

auch Sie in der ersten Zeile der Ausgabe sehen können, heißt es linkes Kind von 90 90 ist das nicht richtig ist. Was ist das?

current node is: 90 its left child is90 its right child is 87 

UPDATE: Wenn ich die Größe auf 8 gesetzt bekomme ich diesen Fehler:

Exception in thread "main" current node is: 90 its left child is90 its right child is 87 
current node is: 87 its left child is28 its right child is 18 
current node is: 28 its left child is12 its right child is 9 
current node is: 18 its left child is8 its right child is 1 
java.lang.ArrayIndexOutOfBoundsException: 9 
    at Heap.print(Heap.java:86) 
    at Heap.main(Heap.java:104) 
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method) 
    at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62) 
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43) 
    at java.lang.reflect.Method.invoke(Method.java:497) 
    at com.intellij.rt.execution.application.AppMain.main(AppMain.java:144) 

Process finished with exit code 1 

UPDATE: Ich dachte, wenn ich den Einsatz der folgenden würde helfen, aber nicht zu ändern:

public void insert(int n) { 
     size++; 
     heap[size] = n; 
     int tmpLocation = size; 
     if (tmpLocation!=1) { 
      while (heap[tmpLocation] > heap[parent(tmpLocation)]) { 
       swap(tmpLocation, parent(tmpLocation)); 
       tmpLocation = parent(tmpLocation); 
      } 
     } 


    } 

Answer 1

Der Täter ist diese Zeile:

heap[++size] = n; 

Wenn Sie das erste Element einfügen, fügen Sie an Position 1 ein, und mit den von Ihnen durchgeführten Schritten erhält haufen [0] & haufen [1] nach jeder Einfügung dieselben Werte. Deshalb sehen Sie, dass das übergeordnete und das linke Kind nach jedem Einfügen denselben Wert haben.

Wenn Sie beispielsweise das erste Element einfügen, versuchen Sie, in den Heap [1] einzufügen und einen Wechsel zwischen Heap [0] & heap [1] durchzuführen. Das Ergebnis ist, dass Sie dieselben Werte im Heap [0] & Heap [1] haben.

Answer 2

In Ihren Methoden insert und remove wird davon ausgegangen, dass der Stammknoten heap[1] ist. Aber Ihre print Methode denkt, dass der Stammknoten in Ihrem Heap um heap[0] ist. Das wird dich in alle möglichen Schwierigkeiten bringen.

Beachten Sie auch, dass Ihre remove Methode size nicht dekrementiert.