数组堆化的递推和递归算法
package org.iSun.heisedeyueya;public class Heap {public static void main(String args[]) {int[] array = new int[] { 24, 10, 90, 77, 16, 25, 33, 89, 67 };Heap.miniHeap(array, array.length);print(array);}/** * 构造最小堆 * * @param array * @param n */public static void miniHeap(int[] array, int n) {int currentPos = (n - 2) >>> 1;// 计算第一个非叶子节点的位置while (currentPos >= 0) {// 递推循环直到堆顶位置recursionFilterDown(array, currentPos);// recurrenceFilterDown(array, currentPos);currentPos--;}}/** * 交换 * * @param array * @param i * @param j */public static void swap(int[] array, int i, int j) {int temp = array[i];array[i] = array[j];array[j] = temp;}/** * 递归算法 * * @param array * @param currentPos * 当前的位置作为父亲节点 */public static void recursionFilterDown(int array[], int currentPos) {// 左孩子的位置int leftChild = currentPos * 2 + 1;// 右孩子的位置int rightChild = leftChild + 1;// 递归结束if (rightChild >= array.length || leftChild >= array.length)return;// 选择较小的孩子int minChild = array[leftChild] > array[rightChild] ? rightChild: leftChild;// 如果父亲节点的值大于较小的孩子那么交换if (array[currentPos] > array[minChild])swap(array, currentPos, minChild);// 递归调用，将孩子节点作为当前节点recursionFilterDown(array, minChild);}/** * 递推算法 * * @param array * @param currentPos */public static void recurrenceFilterDown(int array[], int currentPos) {// 左孩子位置int child = currentPos * 2 + 1;while (child < array.length) {if (child + 1 < array.length && array[child + 1] < array[child])child++;// 已经满足小顶堆，直接跳出循环if (array[child] > array[currentPos])break;else {// 不满足就交换swap(array, child, currentPos);currentPos = child; // 改变当前节点为孩子节点child = 2 * currentPos + 1;// 计算孩子节点的位置}}}public static void print(int[] array) {for (int i = 0; i < array.length; i++) {System.out.print(array[i] + " ");}}}