public class Solution {
public void heapify(int[] A) {
// only heapify the parent nodes from 0 to A.length-1/2
// from bottom to up, call minHeapify()
for (int i=(A.length-1)/2; i>=0; i--) {
minHeapify(i, A);
}
}
public void minHeapify(int i, int[] A) {
while (2*i+1 < A.length) {
// A[son] is the minimum of the two children
int son = 2*i+1;
if (2*i+2<A.length && A[son] > A[2*i+2]) {
son = 2*i+2;
}
if (A[son] >= A[i]) {
break;
}
// swap the minimum with parent
int temp = A[son];
A[son] = A[i];
A[i] = temp;
// check if son is a heap
i = son;
}
}
}
转载请注明原文地址: https://ju.6miu.com/read-1032.html