小九的酒窝

堆的特性：
1、必须是完全二叉树
2、任一结点的值是其子树所有结点的最大值或最小值

Tips:

最大值时，称为“最大堆”，也称大顶堆；

最小值时，称为“最小堆”，也称小顶堆。

        public class MinHeap<E extends Comparable<E>> {
        private List<E> data;

        public MinHeap(int capacity) {
            data = new ArrayList<>(capacity);
        }

        public MinHeap() {
            data = new ArrayList<>();
        }

        // 返回堆中的元素个数
        public int size() {
            return data.size();
        }

        // 返回一个布尔值, 表示堆中是否为空
        public boolean isEmpty() {
            return data.isEmpty();
        }

        // 返回完全二叉树的数组表示中，一个索引所表示的元素的父亲节点的索引
        private int parent(int index) {
            return (index - 1) / 2;
        }

        // 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引
        private int leftChild(int index) {
            return index * 2 + 1;
        }

        // 返回完全二叉树的数组表示中，一个索引所表示的元素的右孩子节点的索引
        private int rightChild(int index) {
            return index * 2 + 2;
        }

        /**
         *
         * @param i
         * @param j
         */
        public void swap(int i, int j) {
            if (i < 0 || i >= size() || j < 0 || j >= size())
                throw new IllegalArgumentException("Index is illegal.");

            E temp = data.get(i);
            data.set(i, data.get(j));
            data.set(j, temp);
        }
        /**
         * index 为i位置元素上浮。
         *
         * @param i
         */
        private void siftUp(int i) {
            //特性2：比较插入值和其父结点的大小关系，小于父结点则用父结点替换当前值，index位置上升为父结点
            // 当上浮元素大于父亲，继续上浮。并且不能上浮到0之上
            // 直到i 等于 0 或 比 父亲节点小了。
            while (i > 0 && data.get(i).compareTo(data.get(parent(i))) > 0) {
                // 数组Array中添加方法swap
                swap(i, parent(i));
                i = parent(i); // 这句话让i来到新的位置，使得循环可以查看新的位置是否还要大。
            }
        }
        /**
         * 堆中添加元素方法。
         *
         * @param e
         */
        public void add(E e) {
            //特性1：新插入的元素首先放在数组最后，保持完全二叉树的特性
            data.add(e);
            siftUp(data.size() - 1);
        }

        public E findMin() {
            return data.get(0);
        }

        public E extractMin() {

            E ret = findMin();

            swap(0, data.size() - 1); // 0位置元素和最后一个元素互换。
            data.remove(data.size() - 1); // 删除此时的最后一个元素(最小值)
            siftDown(0); // 对于0处进行siftDown操作

            return ret;
        }

        /**
         * k位置元素下移
         *
         * @param k
         */
        private void siftDown(int k) {

            while(leftChild(k) < data.size()){
                int j = leftChild(k); // 在此轮循环中,data[k]和data[j]交换位置
                if( j + 1 < data.size() &&
                        data.get(j + 1).compareTo(data.get(j)) < 0 )
                    j ++;
                // data[j] 是 leftChild 和 rightChild 中的最小值

                if(data.get(k).compareTo(data.get(j)) >= 0 )
                    break;

                swap(k, j);
                k = j;
            }
        }
    }

知道了堆的实现，那么堆排序就比较简单了。
第一步：让数组形成堆有序状态；
第二步：把堆顶的元素放到数组最末尾，末尾的放到堆顶，在剩下的元素中下沉到正确位置，重复操作即可。

时间复杂度

堆排序一开始需要将n个数据存进堆里，所需时间为O(nlogn)。排序过程中，堆从空堆的状态开始，逐渐被数据填满。由于堆的高度小于log(2)n ，所以插入 1 个数据所需要的时间为logn。
每轮取出最大的数据并重构堆所需要的时间为O(logn)。由于总共有n轮，所以重构后排序的时间也是O(nlogn)。因此，整体来看堆排序的时间复杂度为O(nlogn)。