Max Heapify issue

Question

Я пробовал отлаживать этот код часами. Я не знаю, почему это не переупорядочивает условия. Я пробовал все, что мог придумать. Может кто-нибудь помочь? Благодарю.

public void heapify(int i) // utility routine to percolate down from index i 
{ 
    printHeap(); 
    int left, r, min; 
    Process tmp; 

    left = lchild(i);   // left child 
    r = rchild(i);     // right child 

    if(left < size() && A[left].compareTo(A[i])<0)  // find smallest child 
     min = left;     // save index of smaller child 
    else 
     min = i; 

    if(r < size() && A[r].compareTo(A[min])<0) 
     min = r;    // save index of smaller child 

    if(min != i)    // swap and percolate, if necessary 
    { 
     tmp = A[i];    // exchange values at two indices 
     A[i] = A[min]; 
     A[min] = tmp; 
     heapify(min); 

     // call heapify 
    }// end if 
printHeap(); 
}// end method heapify 


private int lchild(int i) { 
    return 2 * i + 1; 
} 

private int rchild(int i) { 
    return 2 * i + 2; 
} 

Даже когда я звоню heapify на каждом элементе кучи это не работает:/ Вот CompareTo. Предполагается, что максимальная куча должна распределяться с использованием приоритета, а затем, если есть привязка, она переходит к уникальной полученной по времени стоимости.

public int compareTo(Process o) { 
    int val; 
    if (this.priority > o.getPriority()) { 
     val = -1; 
    } else if (this.priority == o.getPriority()) { 
     if (this.arrivalTime < o.getArrivalTime()) { //Earlier time 
      val = -1; 
     } else { 
      val = 1; 
     } 
    } else { 
     val = 1; 
    } 

    return val; 
} 

Answer 1

Самый быстрый известный способ организовать массив в куче называется Floyd's Algorithm. Вы начинаете посередине массива и перемещаетесь к корню, просеивая каждый элемент по мере необходимости. В вашем случае:

for (int i = size()/2; i >= 0; --i) 
{ 
    heapify(i); 
} 

Вы должны быть в состоянии вызвать функцию heapify, что вы в комплект поставки.

Чтобы увидеть, как это работает, посмотрите на https://stackoverflow.com/a/39020777/56778

Answer 2

Я понял это. В конце концов, это не было проблемой в этом методе. Всем спасибо!