数组堆化 Java 实现

方法一，使用一个新的数组

public Integer[] heapify(Integer[] source) {
        Integer[] target = new Integer[source.length + 1];
        for (int i = 0; i < source.length; i++) {
            target[i + 1] = source[i];
            insert(target, i + 1);
        }
        return target;
    }

    /**
     * 插入值
     * @param target 堆数组
     * @param position 插入的位置
     */
    private void insert(Integer[] target, int position) {
        //当子节点有父节点且值大于父节点值时，交换
        while ((position / 2 > 0) && (target[position] < target[position / 2])) {
            swap(target, position);
            position = position / 2;
        }
    }

    private void swap(Integer[] target, int position) {
        int temp = target[position];
        target[position] = target[position / 2];
        target[position / 2] = temp;
    }

方法二，原地堆化

在方法一的基础上再优化一下，改为原地排序

public void heapify(Integer[] source) {
        for (int i = 0; i < source.length; i++) {
            int position = i;
            int parent = getParent(position);
            //如果节点有父节点且值小于父节点，交换
            while ((position > 0) && (source[position] < source[parent])) {
                swap(source, position);
                position = parent;
                parent = getParent(position);
            }
        }
    }

    /**
     * 计算父节点下标
     */
    private int getParent(int child) {
        return (child + 1) / 2 - 1;
    }

    private void swap(Integer[] target, int position) {
        int temp = target[position];
        int parent = getParent(position);
        target[position] = target[parent];
        target[parent] = temp;
    }

附：提供一个简单打印树结构数组的小工具

/**
 * 简单数组树打印工具
 * Created by zhangkai on 2019/5/2 19:26
 */
public class TreeTool {
    public static void printTree(Object[] array) {
        int length = array.length;
        int layer = getLayer(length);
        for (int i = 0; i < layer; i++) {
            int range = (int) Math.pow(2, i) - 1;
            for (int j = range; j < 2 * range + 1 && j < length; j++) {
                System.out.print(array[j].toString() + "   ");
            }
            System.out.println();
        }
    }

    /**
     * 计算完全二叉树的层数
     * @param x 树元素的个数
     * @return 层数
     */
    private static int getLayer(double x) {
        double value = Math.log(x + 1) / Math.log(2);
        if (value % (int) value > 0) {
            return (int) value + 1;
        }
        return (int) value;
    }
}