所谓堆，是满足如下条件的一个序列：n个元素，任意第i个元素具备同时不比2i和2i+1个元素小或者大。把堆看成一个完全二叉树，那么这棵树所有左右子节点都要具备同时不比父节点小或者大。

从堆得定义可以看出序列的第一个元素，也就是堆顶元素一定是整个序列里最大或者最小的元素。堆排序就是利用了堆的这一特性来实现的。

堆排序可以简单文字描述如下：1.把一个无序序列调整成一个堆；2.输出堆顶元素，然后把剩下的序列调整成堆。3.如果堆还有元素，继续做操作2。

怎么把一个无序序列调整成一个堆呢？父节点和子节点根据条件不停调整可以得到一个堆，这个过程称之为筛选。把这个序列看成一个完全二叉树，最后一个非叶子节点是第n/2求整个元素，筛选只需要从这一个元素开始递减一直到第一个元素即可。

接着说说取走堆顶元素后，怎么调整这个堆：从堆顶拿走一个最大或者最小值后，把堆得最后一个元素放到堆顶，这时堆顶的两个子节点仍然是堆，这时我们沿着堆顶开始向下筛选，很快就能得到一个新堆了。

堆排序java实现代码：

Java代码
  1. public class HeapSort extends BaseSort
  2. {
  3.  
  4. @Override
  5. protected void sortAlg(int[] ls)
  6. {
  7. buildHeap(ls, ls.length - 1);
  8. hsort(ls, ls.length - 1);
  9. }
  10.  
  11. private void hsort(int[] ls, int end)
  12. {
  13. swap(ls, 0, end);
  14. for(int i = end-1; i > 0; i--)
  15. {
  16. maxHeapifyk(ls, 0, i);
  17. swap(ls, 0, i);
  18. }
  19. }
  20.  
  21. private void buildHeap(int[] ls, int end)
  22. {
  23. for(int i = ((end - 1) >> 1); i >= 0; i--)
  24. {
  25. maxHeapifyk(ls, i, end);
  26. }
  27. }
  28.  
  29. /**
  30. * Ki>=K2i Ki>=K2i+1
  31. *
  32. * @param ls
  33. * @param i
  34. */
  35. private void maxHeapifyk(int a[], int i, int end)
  36. {
  37.  
  38. int maxIndex = i;
  39. int finish = (end - 1) >> 1;
  40. for(int j = i; j <= finish;)
  41. {
  42. int left = (j << 1) + 1;
  43. int right = left + 1;
  44. if(left <= end && a[left] > a[j])
  45. maxIndex = left;
  46. if(right <= end && a[right] > a[maxIndex])
  47. maxIndex = right;
  48. if(maxIndex != j)
  49. {
  50. swap(a, maxIndex, j);
  51. j = maxIndex;
  52. }
  53. else
  54. {
  55. break;
  56. }
  57. }
  58. }
public class HeapSort extends BaseSort{    @Override    protected void sortAlg(int[] ls)    {        buildHeap(ls, ls.length - 1);        hsort(ls, ls.length - 1);    }    private void hsort(int[] ls, int end)    {        swap(ls, 0, end);        for(int i = end-1; i > 0; i--)        {            maxHeapifyk(ls, 0, i);            swap(ls, 0, i);        }    }    private void buildHeap(int[] ls, int end)    {        for(int i = ((end - 1) >> 1); i >= 0; i--)        {            maxHeapifyk(ls, i, end);        }    }    /**     * Ki>=K2i Ki>=K2i+1     *      * @param ls     * @param i     */    private void maxHeapifyk(int a[], int i, int end)    {        int maxIndex = i;        int finish = (end - 1) >> 1;        for(int j = i; j <= finish;)        {            int left = (j << 1) + 1;            int right = left + 1;            if(left <= end && a[left] > a[j])                maxIndex = left;            if(right <= end && a[right] > a[maxIndex])                maxIndex = right;            if(maxIndex != j)            {                swap(a, maxIndex, j);                j = maxIndex;            }            else            {                break;            }        }    }

堆排序的时间复杂度稳定在O(nlogn)