1、什么是堆

堆可以看做是一个完全二叉树，可以将一个array[0……n-1]的数组的顺序的看成是一个堆，因此他具有如下特点

父节点Parent(i): parent(i)←A[floor((i−1)/2)]

左节点Left(i): left(i)←A[2∗i+1]

右节点Right(i): right(i)←A[2∗i+2]

1.1、大根堆

从根出发，每一个节点的左右节点都小于等于节点的值；

1.2、小根堆

从根出发，每一个节点的左右节点都大于等于节点的值；

2、算法

1、构造大根堆（从最后一个节点的父节点开始构造）；

2、取出堆顶元素并合堆最后的节点对换位置；

3、去除堆尾的元素 剩下的堆继续构造大根堆（从上到下，从左到右开始构造）；

3、代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
package com.xuecx.sort;

/**
 * @author:xuecx
 * @descript:<p>堆排序工具类，时间复杂度为O(n*lg n) </p>
 * @date:2019/3/20
 */
public class HeapSortUtil {
    /**
     * 1、构建最大堆,从堆的最后一个非叶子节点开始；
     * 2、查找父节点的方法是  既是节点下标/2 取整就是父节点；
     * 3、对于最后一个节点的父节点，既是(n-1)/2；
     * @param array
     * @return
     */
    private int[] buildMaxHeap(int[] array) {
        int n = array.length;
        for (int i = (n - 1) / 2; i >= 0; i--) {
            adjustDownToUp(array, i, n);
        }
        return array;
    }

    /**
     * 自顶向下处理堆，自左向右
     *1、从下标为k的节点开始，需要找到他的左右节点做比较，先让左右节点做比较，取节点大的一个和k节点做比较
     *   left[i]=A[2*k+1]
     *   right[i]=[2*k+2]
     * 2、如果A[K]大于等于A[i]，则循环停止，否则A[K]和A[i]替换；
     * 3、注意替换后，还要判断此时的A[i]的子树，因此还要继续循环判断，下一个判断点为i=2*i+1,直到i>n时停止，同时注意替换后下标k的值要变成当前i
     * @param array
     * @param k 构建堆过程中需要处理的节点
     * @param n 数组成都
     */
    private void adjustDownToUp(int[] array, int k, int n) {
        int temp = array[k];
        //k节点的左孩子=2*k+1,在下一个左孩子=2*i+1,左右子树只会处理一次
        for (int i = 2 * k + 1; i < n - 1; i = 2 * i + 1) {
            if (i < n && array[i] < array[i + 1]) {
                //右节点大，需要和右节点替换
                i++;
            }
            if (temp > array[i]) {
                break;
            } else {
                array[k] = array[i];
                k = i;
            }
            array[i] = temp;
        }
    }

    /**
     * 堆排序方法
     * 1、构建大根堆；
     * 2、堆顶元素和堆尾元素替换；
     * 3、去除堆尾元素继续构建大根堆；其实就是循环的时候不处理最后一个节点
     * @param array
     * @return
     */
    public int[] heapSort(int[] array) {
        array = buildMaxHeap(array);
        for (int i = array.length-1; i > 1; i--) {
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            //第一次运行后i的值比原来的数组已经少1,
            adjustDownToUp(array, 0, i);
        }
        return array;
    }

    public static void main(String[] args) {
        HeapSortUtil heapSortUtil=new HeapSortUtil();
        int[] array={11,21,6,7,23,18,15,4,13};
        int[] ints =heapSortUtil.heapSort(array);
        for (int anInt : ints) {
            System.out.print(anInt+",");
        }
        System.out.println();
    }
}