堆的特点

       堆是一种完全二叉树的模拟，堆一般是基于数组的实现，堆分大顶堆和小顶堆，大顶堆就是堆顶是最大的数据，然后子节点总比父节点小，小顶堆则反过来。java中的优先队列就是一个小顶堆的实现。

PriorityQueue的实现

堆的操作

        关于堆的操作，主要就是两个。siftUp和siftDown，一个是向上调整堆，一个是向下调整堆。调整的时候java有一个使用comparator的调整，一个没有comparator的调整，调整方法基本相似，区别只是比较的时候是否使用comparator，下面主要说不是用comparator的。调整的目的是满足堆的特点。

        调整的代码比较简单，加的注释已经可以疏通逻辑了。   

    private void siftUpComparable(int k, E x) {          //k就是元素的位置，x就是数组中k位置上的元素         Comparable<? super E> key = (Comparable<? super E>) x;         //由于是向上调整，堆顶是没有上的，所以条件就是k>0         while (k > 0) {             //在数组中，下标(k-1)/2就是父节点的位置             int parent = (k - 1) >>> 1;             Object e = queue[parent];             //java的实现是小顶堆，所以这里判断是父元素小于比较元素就表示堆调整完成             if (key.compareTo((E) e) >= 0)                 break;             //交换             queue[k] = e;             //原来的树已经满足，被交换的节点，都满足比父节点小，比子节点大，             //由于元素交换了，说明现在的元素比较小             //得继续调整，如果还能被调整，调整换下来的元素还是比较大的             k = parent;         }         queue[k] = key;     }     private void siftDownComparable(int k, E x) {         Comparable<? super E> key = (Comparable<? super E>)x;         int half = size >>> 1;         //由于是向下调整，所以最后一个有子节点的节点是（len-1）/2，没有子节点的就不用调整                 while (k < half) {             int child = (k << 1) + 1;              Object c = queue[child];             int right = child + 1;             //找出两个子节点中最小的比较，因为是小顶堆             if (right < size &&((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)                 c = queue[child = right];             //父都比子小就结束             if (key.compareTo((E) c) <= 0)                 break;             queue[k] = c;             //由于元素交换了，下面的树形结构也得满足结构，所以继续调整             k = child;         }         queue[k] = key;     }

         很明显向上调整是有一个有条件操作，向下调整则是没有特殊调整的。所以这两个操作使用的地方也是不同的。

siftDown的应用

    siftDown主要是用来堆的建立。

    private void heapify() {         //所有有子节点的元素进行堆的建立         for (int i = (size >>> 1) - 1; i >= 0; i--)             siftDown(i, (E) queue[i]);     }      public E poll() {         if (size == 0)             return null;         int s = --size;         modCount++;//这个主要是在并发操作时抛出异常的，并不是线程安全集合         E result = (E) queue[0];         //取出最后一个元素，然后被当做第一个元素，重新调整堆         E x = (E) queue[s];         queue[s] = null;         //由于原来的部分已经是堆，所以就相当于堆顶没有调整         if (s != 0)             siftDown(0, x);         return result;     }

shifUp的应用

shifUp则是在现有成堆的情况下去添加元素的。

    public boolean offer(E e) {         if (e == null)             throw new NullPointerException();         //modCount是用来多线程环境下抛出异常的         modCount++;         int i = size;         if (i >= queue.length)             grow(i + 1);         size = i + 1;         if (i == 0)             queue[0] = e;         else             siftUp(i, e);//新元素被当在最后，开始向上调整         return true;     }

 PriorityQueue的其余点

 构造函数

   PriorityQueue在构造函数中做了一个分类的优化

    public PriorityQueue(Collection<? extends E> c) {         if (c instanceof SortedSet<?>) {             SortedSet<? extends E> ss = (SortedSet<? extends E>) c;             this.comparator = (Comparator<? super E>) ss.comparator();             initElementsFromCollection(ss);         }         else if (c instanceof PriorityQueue<?>) {             PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;             this.comparator = (Comparator<? super E>) pq.comparator();             initFromPriorityQueue(pq);         }         else {             this.comparator = null;             initFromCollection(c);         }     }

SortedSet本身是排序的，所以可以直接把数据拷贝到priorityqueue中。

    private void initElementsFromCollection(Collection<? extends E> c) {         Object[] a = c.toArray();         if (a.getClass() != Object[].class)             a = Arrays.copyOf(a, a.length, Object[].class);         int len = a.length;         if (len == 1 || this.comparator != null)             for (int i = 0; i < len; i++)                 if (a[i] == null)                     throw new NullPointerException();         //获取元素和长度         this.queue = a;         this.size = a.length;     }

    PriorityQueue一般也是排序的，但是这里做了一个防备，就是对于继承PriorityQueue的部分需要另外对待。java默认没有它的子类，这里是防止开发者自己的实现，万一不是排序或者堆的情况，直接拷贝数组是有问题的。

    private void initFromPriorityQueue(PriorityQueue<? extends E> c) {         if (c.getClass() == PriorityQueue.class) {             this.queue = c.toArray();             this.size = c.size();         } else {             //PriorityQueue的不确定子类             initFromCollection(c);         }     }

    剩下的情况都是依靠initFromCollection来的。其实主要就是下面的两个步骤。

    private void initFromCollection(Collection<? extends E> c) {         //拷贝数组         initElementsFromCollection(c);         //建堆         heapify();     }

初始化元素大小

    现在面试有一些会问这个，所以说一下，初始化11，arrayList是10，之所以不同应该是11正好是一个满二叉树的数字。

private static final int DEFAULT_INITIAL_CAPACITY = 11;

扩容

        说这个也是因为面试可能会问。原来的长度小于64，就直接涨一倍再加2，否则涨0.5倍。至于为什么非要+2，我也不清楚。除了hash结构，扩容有hash计算方便问题，剩下的还没发现扩容有什么特别的讲究。

    private void grow(int minCapacity) {         int oldCapacity = queue.length;         //原来的长度小于64，就直接涨一倍再加2，否则涨0.5倍         int newCapacity = oldCapacity + ((oldCapacity < 64) ?                                          (oldCapacity + 2) :                                          (oldCapacity >> 1));         if (newCapacity - MAX_ARRAY_SIZE > 0)             newCapacity = hugeCapacity(minCapacity);         queue = Arrays.copyOf(queue, newCapacity);     }

堆排序

       堆排序就是先建立堆，然后移除第一个数，剩下的部分继续调整堆，这样每次都是拿出剩下中最大或者最小的元素，这样就是排序了。

      linux中sort函数也是堆排序的实现，而且上面有一段注释

/**   43 * sort - sort an array of elements   44 * @base: pointer to data to sort   45 * @num: number of elements   46 * @size: size of each element   47 * @cmp_func: pointer to comparison function   48 * @swap_func: pointer to swap function or NULL   49 *   50 * This function does a heapsort on the given array. You may provide a   51 * swap_func function optimized to your element type.   52 *   53 * Sorting time is O(n log n) both on average and worst-case. While   54 * qsort is about 20% faster on average, it suffers from exploitable   55 * O(n*n) worst-case behavior and extra memory requirements that make   56 * it less suitable for kernel use.   57 */

这里和快排对比说明了为什么选择堆排序。

1，时间复杂度

    堆排序的平均时间复杂度为O(nlogn),最坏情况也是O(nlogn)，快排的平均时间复杂度也是O(nlogn)，但是最坏情况是O(n*n)。

2，空间复杂度

    堆排序是O(1)，快排是O(logn)。快排是递归调用，所以空间要求更多一些。

    其实这样比较，感觉堆排序怎么也比快排更好，但是众所周知，快排是内排序最快，而且注释也说明平均情况下，快排是比堆排序快20%的。那问题来了，为什么会这样呢？

堆排序为什么比快排慢

    首先时间复杂度的计算本身是一个忽略一些情况的估算，其实和程序执行的结果不完全一致，例如程序中有比较，交换数值的操作，但是这些并不会作为评估时间复杂度的方式，但是这些是程序执行的一个操作。时间复杂度只能保证数量级直接的比较，例如nlogn是比n*n快的，但是并不代表nlogn和nlogn的执行是一样快的。

    堆排序相比快排，浪费时间的一个点就是在做无效的比较交换。例如大顶堆，最上面的元素是最大的，堆排序会把最大的拿出来，然后把当时的最后一个换上去，继续建立堆。这里有个很明显的问题，就是在一次堆建立后，从最后拿的元素没有原来堆顶下面两个元素大，那么就有很多无用的比较交换，其实本来就小，还得和大的都比较一次并且换位置。这里是堆排序的一个优化点，很多人都在这里做了优化方案。

    交换次数可以通过下面这个网站对比模拟。http://sorting.at/

堆排序的应用

      例如对最差时间有要求的场景，例如上面说的sort的例子

      大数据量的筛选：求一亿个数字里面最小的10个数字（剑指offer题目）