/** * 构建大顶堆 * * @param a 数组 * @param n 最后一个元素下标 */ publicstaticvoidbuildHeap(int[] a, int n){ // 从最后一个非叶子节点开始,倒序依次处理其它非叶子节点 for(int i = (n -1) / 2; i >=0; i--) { heapify(a, n, i); } }
/** * 堆化 * * @param a 数组 * @param n 最后一个元素下标 * @param i 需要调整的父节点下标 */ publicstaticvoidheapify(int[] a,int n, int i){ while (true) { // 大顶堆规则:替换节点为当前节点和叶子节点中值最大的节点 int maxPos = i;
int l = 2 * i + 1; if (a[l] > a[maxPos]) { maxPos = l; }
int r = 2 * i + 2; if (a[r] > a[maxPos]) { maxPos = r; }
// 当前节点最大时退出 if (maxPos == i) { return; }
swap(a, maxPos, i);
// 保证叶子节点也满足堆化规则 i = maxPos; } }
publicstaticvoidswap(int[] a, int i, int j){ int tmp = a[i]; a[i] = a[j]; a[j] = tmp; }