堆

对于Java语言比较熟悉的同学应该都对堆有所耳闻。新建对象会存放在堆中，临时变量，方法入参和方法体会存放在栈中。这其实是计算机中内存结构，而对于数据结构中的堆来说是完全不同的概念。

定义：堆是一个完全二叉树，并且任一节点都大于等于（或小于等于）其左右子节点。

任一节点大于等于左右子节点的堆叫做大顶堆。

任一节点小于等于左右子节点的堆叫做小顶堆。

前面讲过完全二叉树适合使用数组进行存储，除了第一个数组元素浪费之外，其它数组元素都是连续的，内存的利用率很高。

堆常用的操作是插入和删除

插入：堆插入数据后还需要维持其定义的两个特征，为了保持其完全二叉树特征，数据直接插入到堆最后。然后不停对比插入数据和父类的大小，大于父类就进行交换，直到条件终止。

a表示数组，count表示当前个数，n表示总个数

删除：堆删除数据先查找需要删除的数据，使用堆最后的数据进行替代，从而堆依旧保持了其完全二叉树特征，然后通过对比替代类和父类的大小，小于就进行交换，直到条件终止，或者对比其与子类的大小，大于就进行交换，直到条件终止。

从插入和删除操作可以知其时间复杂度都跟树的高度成正相关。

完全二叉树的高度=logn。所以时间服务度 = O(logn)。

堆排序

在日常开发中你可能没有看过堆排序的源码，但是你或多或少应该都听到过堆排序的概念。

堆排序：包括建堆和排序两个过程。建堆就是非叶子节点元素不断堆化的一个过程，最后就可以形成一个堆。堆化后只需要取第一个元素即是最大或最小元素，与最后一个元素交换，然后再进行一次堆化即可。

如果是顺序的话：先建立一个大顶堆，然后不停把堆顶元素和堆最后一个元素替换后，再对堆顶元素进行堆化。

如果是逆序的话：先建立一个小顶堆，然后不停把堆顶元素和堆最后一个元素替换后，再对堆顶元素进行堆化。

对比一下堆排序和快排

1，堆排序数据访问的方式没有快速排序友好。对于快速排序来说，数据是顺序访问的。而对于堆排序来说，数据是跳着访问的。这样对CPU不是很友好。

2，对于堆排序来说，数据交换的次数大于快速排序算法。

所以在实际开发中堆排序算法没有快速排序算法性能好。