[数据结构与算法]树形选择排序

树形选择排序一个很重的条件就是：所排序的数组个数必须是2的次幂，这样才能满足完全二叉树的形态，如果不是2的次幂，则用无穷大值去填充，使其个数称为2的次幂。

代码如下：

  /**
     * 树形选择排序。
     * 注意：datas的长度必须满足2的k次幂。
     *
     * @param datas 待排序数据
     */
    public static void treeSelectionSort(int[] datas) {
        int length = datas.length; // 待排序的数组长度，length一定要是2的幂次方，如果不是则扩大到2的幂次方

        if (!((length & (length - 1)) == 0)) {// 判断length是否是2的幂次方
            int minPower = minPower(length);
            length = (int) Math.pow(2, minPower + 1);
        }
        int treeSize = length * 2 - 1; // 树的存储大小
        int[] tree = new int[treeSize]; // 树的存储空间

        // 由后向前将待排序数据存储在树中（叶子节点）
        for (int i = length - 1, j = treeSize - 1; i >= 0; i--, j--) {
            if (i > datas.length - 1) {
                tree[j] = MAX;
            } else {
                tree[j] = datas[i];
            }
        }
        // 填充非叶子节点
        for (int i = treeSize - 1 - length; i >= 0; i--) {
            tree[i] = Integer.min(tree[2 * i + 1], tree[2 * i + 2]);
        }
        PrintUtil.printIntArray(tree);


        // 排序
        int i = 0;
        while (i < datas.length) {
            int minValue = tree[0];
            datas[i] = minValue; // 最小值

            // 将树中次最小值替换为无穷大值
            int minIndex = 0;// 最小值下标
            while (true) {
                int a = (minIndex + 1) * 2 - 1;
                int b = (minIndex + 1) * 2;
                if (a > tree.length - 1 || b > tree.length - 1) {
                    break;
                }
                int v1 = tree[a];
                int v2 = tree[b];
                // 将最小值的结点置为无穷大
                minIndex = Math.min(v1, v2) == v1 ? a : b;
                tree[minIndex] = MAX;
            }

            // 重新选择生成胜利树，找出最小值
            while (minIndex > 0) {
                if (minIndex % 2 == 0) {
                    tree[minIndex / 2 - 1] = Math.min(tree[minIndex], tree[minIndex - 1]);
                    minIndex = minIndex / 2 - 1;
                } else {
                    tree[minIndex / 2] = Math.min(tree[minIndex], tree[minIndex + 1]);
                    minIndex = minIndex / 2;
                }
            }
            i++;
        }
    }

    /**
     * 求number的2的对数
     */
    private static int minPower(int number) {
        for (int i = 1; i < Integer.MAX_VALUE; i++) {
            if (Math.pow(2, i) < 10 && Math.pow(2, i + 1) > 10) {
                return i;
            }
        }
        return -1;
    }