堆排序
堆排序使用的是二叉堆，它是一棵完全二叉树。堆有大顶堆和小顶堆之分。
堆的一些性质：
① ：它是一颗完全二叉树。
② ：每个节点大于（小于）或等于它的任意一个孩子。
表示堆的二叉树中，除了最底层外，该树是完全充满的，而且是从左至右填充的。
如果堆的大小是提前可知道的，那么可以将堆存储在一个ArrayList或是一个数组中。（ArrayList底层实现也是一个数组啦！）
存储在数组中的顺序也是一层一层的按从左至右的存储的。
对于位置 i处的结点，它的左孩子在位置 （2i+1）处，它的右孩子在（2i+2）处，它的父亲在位置(（i-1）/ 2 )处。图示：
图：堆 - 1
堆常见的操作：
（一）添加一个新结点
给堆添加一个新结点，首先将新结点添加到堆尾，然后按如下方式（伪代码）重建这棵树：
Let the last node be the current node；
While（the current node is greater than its parent）{
Swap the current node with itsparent；
Now the current node is one levelup；
}
n 以上伪代码参考自《计算机程序设计艺术》第三卷
n
结点添加图示：
图：堆 - 2
（二）删除根结点
在实际的程序中我们需要经常删除堆中元素的堆顶元素（根结点）。在删除根结点后，当前余下的元素可能就违反了堆的性质，这时就需要重建堆，以保证堆的特征不变。
重建堆的算法描述如下：
Move the last node to replace the root；
Let the root be the current node；
n 在删除根元素之后，将当前的堆末尾元素移动到根元素位置，并成为当前元素
n 然后将当前元素和自己的两个孩子结点中最大的一个结点比较大小（如果只有一个孩子结点就直接和孩子结点比较），如果最大的孩子结点小于等于当前结点，则重建堆完成，否则将当前元素和其最大的孩子结点互换，互换之后重复本步操作。
下面将用图示演示删除根元素后重建堆的过程：（以图：堆–1所示堆为例）
图：堆 - 3
建堆：在以上分析的基础上我们可以很快的构建出我们自己的堆（Heap）此处Heap实现底层将采用List实现；
Heap类Java代码：
@SuppressWarnings("rawtypes")
public class Heap<E extends Comparable>{
private java.util.List<E> list = null;
/**
* 默认无参构造器
*/
public Heap(){
list = new java.util.ArrayList<E>();
}
/**
* 根据传入的序列构建一个堆
* @param objects
*/
public Heap(E[] objects){
list = new java.util.ArrayList<E>();
for(int i = 0; i < objects.length; i++){
add(objects[i]);
}
}
/**
* 将一个新结点添加到堆中
* @param newObj
*/
@SuppressWarnings("unchecked")
public void add(E newObj) {
list.add(newObj); // 将新结点添加到最后一个位置上
int currentIndex = list.size() - 1; // currentIndex指向堆中最后一个元素,也即当前元素为最后一个元素
while (currentIndex > 0) {
int parentIndex = (currentIndex - 1) / 2; // 根据堆的性质找到当前结点的父结点
// 当前元素大于其父结点，互换
if (list.get(currentIndex).compareTo(list.get(parentIndex)) > 0) {
E temp = list.get(currentIndex);
list.set(currentIndex, list.get(parentIndex));
list.set(parentIndex, temp);
}else{
break;
}
currentIndex = parentIndex;
} // end_while
}
/**
* 移除堆顶元素
* @return
*/
@SuppressWarnings("unchecked")
public E remove(){
if(list.size() == 0) return null;
E root = list.get(0);
list.set(0, list.get(list.size() - 1)); // 将堆末尾的元素移动到堆顶
list.remove(list.size() - 1); // 删除堆末尾元素，因为此时已经移动到了堆顶
int currentIndex = 0; // 将堆顶元素设置为当前元素
while(currentIndex < list.size()){
int leftChildIndex = 2 * currentIndex + 1; // 堆的性质
int rightChildIndex = 2 * currentIndex + 2;
// 边界判断,并找到当前元素的两个孩子结点中最大的一个
if(leftChildIndex >= list.size())
break;
int maxIndex = leftChildIndex;
if (rightChildIndex < list.size()) {
if (list.get(maxIndex).compareTo(list.get(rightChildIndex)) < 0) {
maxIndex = rightChildIndex;
}
}// end_2_if
if (list.get(currentIndex).compareTo(list.get(maxIndex)) < 0) {
E temp = list.get(maxIndex);
list.set(maxIndex, list.get(currentIndex));
list.set(currentIndex, temp);
currentIndex = maxIndex;
}else{
break;
}
} // end_while
return root;
}
/**
* 返回当前堆的大小
* @return
*/
public int size(){
return list.size();
}
}
堆排序：利用Heap类排序
public class HeapSort {
@SuppressWarnings("rawtypes")
public <E extends Comparable> void heapSort(E[] list){
Heap<E> heap = new Heap<E>(list);
for(int i = list.length - 1; i >= 0; i--){
list[i] = heap.remove();
}
}
}
堆排序的时间复杂度：
堆排序时间复杂度为：O(nlogn)