首先，了解下堆积排序的概念：

• 第一步，将待排序序列转换为堆积树，如果是从小到大排序，那么转换为最小堆积树，如果是从大到小排序，那么就是最大堆积树
• 第二步，取出该堆积树的树根，然后对剩余的数重新组成堆积树，重复第一步

最小堆积树特点：整个序列中，树根是最小的数。
最大堆积树特点：整个序列中，树根是最大的数。

最小堆积树实现的堆积排序如下：

package com.xiaoteng;

import java.util.Arrays;

public class HeapTreeSort {

    // 堆积排序
    // 首先，将待排序的序列转换成最大堆积树或最小堆积树
    // 然后一次取树根
    // 剩余的树重新组成堆积树，重复上述步骤
    // 本实例演示从小到大排序，所以用的是最小堆积树

    public int[] sort(int[] a) {
        // 生成最小堆积树
        int[] b = heapTree(a);
        int[] c = new int[a.length];
        int i = 0;
        while (b.length > 0) {
            System.out.println("当前最小堆积树：" + Arrays.toString(b));
            c[i++] = b[0];
            // 重新生成最小堆积
            if (b.length == 1) {
                break;
            }
            b = heapTree(Arrays.copyOfRange(b, 1, b.length));
        }
        return c;
    }

    public int[] heapTree(int[] a) {
        // 从1开始
        int p;
        for (int i = 1; i < a.length; i++) {
            // 取当前节点的父节点
            p = parentIndex(i);

            int j = i;
            while (p >= 0) {
                if (a[j] < a[p]) {
                    int tmp = a[p];
                    a[p] = a[j];
                    a[j] = tmp;
                }

                // 继续寻找p的父节点
                j = p;
                p = parentIndex(p);
                if (j == p || p < 0) {
                    // 已经到底了，跳出循环
                    break;
                }
            }
        }

        return a;
    }

    public int parentIndex(int i) {
        int p;
        if (i % 2 == 0) {
            // 偶数
            p = i / 2 - 1;
        } else {
            p = (i - 1) / 2;
        }
        return  p;
    }

    public static void main(String[] args) {
        int[] arr = {1, 1, 2, 3, 18, 1, 1000, 3, 19, 99, 29, 190, 2000, 12};
        HeapTreeSort heapTreeSort = new HeapTreeSort();
        System.out.println(Arrays.toString(heapTreeSort.sort(arr)));
    }

}

输出结果：

当前最小堆积树：[1, 1, 1, 3, 18, 2, 12, 3, 19, 99, 29, 190, 2000, 1000]
当前最小堆积树：[1, 1, 3, 18, 2, 12, 3, 19, 99, 29, 190, 2000, 1000]
当前最小堆积树：[1, 2, 3, 3, 12, 18, 19, 99, 29, 190, 2000, 1000]
当前最小堆积树：[2, 3, 3, 12, 18, 19, 99, 29, 190, 2000, 1000]
当前最小堆积树：[3, 3, 12, 18, 19, 99, 29, 190, 2000, 1000]
当前最小堆积树：[3, 12, 18, 19, 99, 29, 190, 2000, 1000]
当前最小堆积树：[12, 18, 19, 99, 29, 190, 2000, 1000]
当前最小堆积树：[18, 19, 99, 29, 190, 2000, 1000]
当前最小堆积树：[19, 99, 29, 190, 2000, 1000]
当前最小堆积树：[29, 99, 190, 2000, 1000]
当前最小堆积树：[99, 190, 2000, 1000]
当前最小堆积树：[190, 2000, 1000]
当前最小堆积树：[1000, 2000]
当前最小堆积树：[2000]
[1, 1, 1, 2, 3, 3, 12, 18, 19, 29, 99, 190, 1000, 2000]