这里的“堆”和Java中的堆并不是一个概念。

堆排序中的“堆”实际上是一个“排列成数组的完全二叉树”，或者说把一个数组展开，当成完全二叉树来看。

即在对数组进行排序时，把数组当做一个“完全二叉树”进行操作，实现排序。

package com.company;/** * Created by pierr on 2017/3/25. * 堆排序 */public class HeapSort {    public int[] heapSort(int[] arr){        HeapArray heapArray = new HeapArray();        heapArray.setArr(arr);        heapArray.setHeapSize(arr.length);        //构建最大堆        buildMaxHeap(heapArray);        for (int i = arr.length-1 ; i>0 ; i--) {            int temp = arr[0];            arr[0] = arr[i];            arr[i] = temp;            heapArray.setHeapSize(heapArray.getHeapSize()-1);            makeMaxHeap(heapArray,0);        }        return heapArray.getArr();    }    /**     * 构建最大堆     * @param heapArray     */    private void buildMaxHeap(HeapArray heapArray){        for (int i = heapArray.getArr().length/2 - 1; i >= 0 ; i--) {            makeMaxHeap(heapArray,i);        }    }    /**     * 将输入的下标和其左右子树中的最小值，移动到比其小的子树的根结点处     * @param heapArray     */    private void makeMaxHeap(HeapArray heapArray,int i){        //左孩子下标,2i        int left = (i<<1)+1;        //右孩子下标2i+1，注意位操作优先级比+要低        int right = (i<<1)+2;        //存储当前考虑的树的size        int heapSize = heapArray.getHeapSize();        //数组对象        int[] arr = heapArray.getArr();        //存储三个数中最大的一个的下标        int largest = i;        if (left
    
     arr[i]){            largest = left;        }        if (right
     
      arr[largest]){            largest = right;        }        //如果父节点不是最大的        if (largest!=i){            //交换            int temp = arr[i];            arr[i] = arr[largest];            arr[largest] = temp;            //继续将父节点处的数"下移"            makeMaxHeap(heapArray,largest);        }    }}/** * 堆结构 */class HeapArray{    //组成堆的数组    private int[] arr;    //堆的size    private int heapSize;    public int[] getArr() {        return arr;    }    public void setArr(int[] arr) {        this.arr = arr;    }    public int getHeapSize() {        return heapSize;    }    public void setHeapSize(int heapSize) {        this.heapSize = heapSize;    }}