在java中弹出并重新排序堆对象的元素

Question

我遇到问题的方法是popTop 我有一个OurProcess数组，它有一个变量名currentPriority，我将这个堆从 最小的排序到最大但popTop只是发回第一个对象，然后离开优先级[0] == null，我似乎无法弄清楚。任何帮助将不胜感激！

public class Queue { 
int number1 = 0; 
final int root = 0; // an easy reference to the root of the heap 
int endPoint = 0; // Endpoint is where the first blank space in in queue is 
int size; // an easier value to work with than the length of the array 
OurProcess[] priorities; // The array that the whole class is built upon 
char location; // This is just shorthand for the name of the object 
Queue(int size, char location) { 
    this.location = location; 
    this.size = size; 
    priorities = new OurProcess[size]; 
} 

Queue(OurProcess[] processesArray, char location) throws Exception { 
    this.location = location; 
    size = processesArray.length; 
    priorities = new OurProcess[processesArray.length]; 
    for (int i = 0; i < processesArray.length - 1; i++) { 
     insert(processesArray[i]); 
    } 
} 

public void insert(OurProcess toAdd) { 

    if (endPoint == priorities.length) { 
     System.out.println("Out of bounds"); 
    } else { 
     endPoint++; 
     priorities[endPoint - 1] = toAdd; 
     siftUp(endPoint - 1); 
    } 
} 

public void siftUp(int nodeIndex) { 
    int parentIndex; 
    OurProcess tmp; 
    if (nodeIndex < priorities.length) { 
     parentIndex = (nodeIndex - 1)/2; 
     while (priorities[parentIndex].currentPriority > priorities[nodeIndex].currentPriority) { 
      tmp = priorities[parentIndex]; 
      priorities[parentIndex] = priorities[nodeIndex]; 
      priorities[nodeIndex] = tmp; 
      siftUp(parentIndex); 
     } 

    } 
} 

public OurProcess popTop() { 
    OurProcess pop = priorities[root]; // Copy the root of our array 
    priorities[root] = priorities[endPoint]; // Place our object at the end 
    priorities[endPoint] = null; 
    int index = root; 
    int leftChild = index*2+1; 
    int rightChild, lesserChild; 
     while(index < priorities.length && priorities[index] != null){ 
      lesserChild = leftChild; 
      rightChild = leftChild + 1; 
      if (priorities[rightChild].currentPriority < priorities[leftChild].currentPriority){ 
       lesserChild = rightChild; 
      } 
      if (priorities[lesserChild].currentPriority < priorities[index].currentPriority){ 
       OurProcess temp = priorities[lesserChild]; 
       priorities[lesserChild] = priorities[index]; 
       priorities[index] = temp; 
       index = lesserChild; 
       leftChild = index*2+1; 
      } 
     } 


    return pop; // Return the top of the array 
} 

}

Answer 1

根据这里的评论：

int endPoint = 0; // Endpoint is where the first blank space in in queue is 

我们可以预期，priorities[endPoint]永远是零。所以这样的：

OurProcess pop = priorities[root]; // Copy the root of our array 
    priorities[root] = priorities[endPoint]; // Place our object at the end 
    priorities[endPoint] = null; 
    int index = root; 

是相同的：

后该：

 while(index < priorities.length && priorities[index] != null){ 

是相同的：

 while(false){ 

我想你实际上意味着使用endPoint - 1（最后一个非空索引）而不是endPoint（第一个空索引），但是您还需要更加关心边缘案例;例如，如果在调用popTop时堆已经为空？

此外，更重要的是—您应该学会调试您的代码，可以使用调试器或使用System.out.println(...)语句来查看各个点上发生了什么。如果你在这里完成了这个任务，你很快就会发现你的代码的哪部分没有达到你的预期。