代码

public class MaxHeap<Data extends Comparable> {
    // 堆中数据
    private Data[] dataList;
    // 堆的容量
    private int capacity;
    // 数据个数
    private int size;

    public MaxHeap(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.dataList = (Data[]) new Comparable[capacity];
    }

    public MaxHeap(Data[] dataList) {
        this(dataList.length);
        for (Data data : dataList) {
            insert(data);
        }
    }

    /**
     * 数据个数
     *
     * @return
     */
    public int size() {
        return size;
    }

    public Data[] data() {
        return dataList;
    }

    /**
     * 插入新元素
     *
     * @param data
     * @return
     */
    public void insert(Data data) {
        if (data == null) {
            return;
        }
        dataList[size++] = data;
        // 若只有一个元素直接返回
        if (size == 1) {
            return;
        }
        // 若两个或两个以上则需要看是否需要调整树结构
        // 当前结点的索引
        int currIndex = size - 1;
        // 调整树结构
        rise(currIndex);
    }

    /**
     * 排序
     */
    public void sort() {
        if (size <= 1) {
            return;
        }
        for (int i = size - 1; i > 0; i--) {
            // 交换第一个数据与i处的数据
            exchange(0, i);
            // 调整树结构
            dive(0, i - 1);
        }
    }

    /**
     * 交换j和k的数据
     *
     * @param j
     * @param k
     */
    private void exchange(int j, int k) {
        Data temp = dataList[j];
        dataList[j] = dataList[k];
        dataList[k] = temp;
    }

    /**
     * 上浮算法
     *
     * @param currIndex
     */
    private void rise(int currIndex) {
        if (currIndex == 0) {
            return;
        }
        // 父结点的索引
        int parentIndex = (currIndex - 1) / 2;
        // 子结点不比父结点大，则表示位置是正确的，不需要调整
        if (dataList[currIndex].compareTo(dataList[parentIndex]) <= 0) {
            return;
        }
        // 子结点比父结点大，则交换
        exchange(currIndex, parentIndex);
        // 调整父结点
        rise(parentIndex);
    }


    /**
     * 下沉算法
     *
     * @param currIndex
     */
    private void dive(int currIndex, int end) {
        if (currIndex >= end) {
            return;
        }
        // 左子结点的索引
        int left = 2 * currIndex + 1;
        // 若当前结点没有左子结点，则不需要调整
        if (left > end) {
            return;
        }
        // 右子结点的索引
        int right = left == end ? -1 : left + 1;
        // 比较左右子结点哪个大
        int maxChildIndex = right == -1 || dataList[left].compareTo(dataList[right]) > 0 ? left : right;
        // 当前结点与大的子结点比较
        if (dataList[currIndex].compareTo(dataList[maxChildIndex]) >= 0) {
            return;
        }
        // 若小于，则交换
        exchange(currIndex, maxChildIndex);
        dive(maxChildIndex, end);
    }
}

测试

    public static void main(String[] args) {
        Integer[] data = {5, 8, 3, 2, 7, 1, 4, 6, 9};
        System.out.printf("排序前数据：%s\n", Arrays.toString(data));
        MaxHeap heap = new MaxHeap(data);
        heap.sort();
        System.out.printf("排序后数据：%s\n", Arrays.toString(heap.data()));
    }

输出结果：

排序前数据：[5, 8, 3, 2, 7, 1, 4, 6, 9]
排序后数据：[1, 2, 3, 4, 5, 6, 7, 8, 9]