一、什么是堆

(二叉)堆数据结构式一种数组对象，它可以视为一颗完全二叉树。树中每个结点与数组中存放该结点值得那个元素对应。树的每一层都是填满的，最后一层除外。

以上图片就是一个堆结构（左侧）与数组（右侧）的对应关系，存储格式依然是数组但是可以把它看成是一个堆结构。需要注意的是图中都是从1开始的，而Java中数组是从0开始的。任意节点i左右子节点数组索引的计算方法: 左子节点是2i ，右子节点是2i+1。以上图为例如果i=4，左子节点索引值=2*i = 2*4 = 8，右子节点索引值= 2*i+1 = 2*4+1 = 9。
但是Java中数组是从0开始，所以在Java中i的左右子节点数组索引的计算方法应该是: 左子节点在数组中索引：2i+1 有子节点在数组中索引：2i+2

二、保持堆的性质

二叉堆分两种：最大堆与最小堆。这两种都必须满足堆的特点，而且如果是最大堆必须保证每层中的父节点都必须大于其左右子节点，最小堆规则与其相反。先来看看如果数组中任意元素进行操作，使其满足最大堆的以上条件。

（1）使数组中任意元素满足最大堆规则的伪码：

MAX-HEAPIFY(A, i)
1 l ← LEFT(i)
2 r ← RIGHT(i)
3 if l ≤ heap-size[A] and A[l] > A[i]
4    then largest ← l
5    else largest ← i
6 if r ≤ heap-size[A] and A[r] > A[largest]
7    then largest ← r
8 if largest ≠ i
9    then exchange A[i] <-> A[largest]
10         MAX-HEAPIFY(A, largest)

（2）以上伪码逐句解释

1. 计算出左子节点索引 2. 计算出右子节点索引 3. 如果左子节点数组索引小于等于数组大小并且左子节点大于父节点 4. 把左子节点数组索引赋值给largest 5. 如果不满足3的条件，把当前父节点的数组索引赋值给largest 6. 如果右子节点数组索引小于等与数组大小并且右子节点数组索引大于largest 7. 如果满足6的条件，右子节点赋值给largest 8. 如果需要交换 9. 把当前父节点与largest（子节点最大值）进行交换 10. 把largest节点当做下一次执行的父节点，接着从1开始执行。

（3）伪码的Java代码实现

	private void maxHeapify(int[] a, int i) {

		int largest;

		int leftIndex = 2 * i + 1;
		int rightIndex = leftIndex + 1;

		if (leftIndex < a.length && a[leftIndex] > a[i]) {
			largest = leftIndex;
		} else {
			largest = i;
		}
		if (rightIndex < a.length && a[rightIndex] > a[largest]) {
			largest = rightIndex;
		}

		if (largest != i) {
			swap(a, i, largest);
			maxHeapify(a, largest);
		}
	}

	public static void main(String[] args) {
		int[] array = { 16, 4, 10, 14, 7, 9, 3, 2, 8, 1 };

		HeapSort heapSort = new HeapSort();
		// Java数组从0开始，第二个元素索引是1
		heapSort.maxHeapify(array, 1);
		System.out.println(Arrays.toString(array));
	}

输入数组：[16, 4, 10, 14, 7, 9, 3, 2, 8, 1] 输出结果：[16, 14, 10, 8, 7, 9, 3, 2, 4, 1]

（4）演示i=2时的执行流程

上图是针对堆中i=2父节点进行堆性质的处理，即保证父节点i的左右子节点的值都比其小，以下是图片具体文字描述的步骤： 1. 先看（a）图，当i=2时 array[i] = array[2] = 4 左子节点 array[leftIndex] = array[4] = 14，判断条件array[leftIndex] > array[i] = true，左子节点比父节点值大不满足最大堆的条件。右子节点array[rightIndex] = array[5] = 7，判断条件array[rightIndex] > (父节点与左子节点最大的值，当前是array[leftIndex]) = false，右子节点比左子节点小，所以左子节点作为父节点满足最大堆的条件。交换i = 2 与 leftIndex = 4 的值，即上图（b）展示的结果
2. 再看（b）图，由步骤1可以决定i = 2节点已经满足最大堆条件，但是需要再次判断交换后的i=4的值是否满足最大堆条件。当i=4时 array[i] = array[4] = 4 左子节点 array[leftIndex] = array[8] = 2，判断条件array[leftIndex] > array[i] = false，左子节点满足最大堆的条件。右子节点array[rightIndex] = array[9] = 8，判断条件array[rightIndex] > (父节点与左子节点最大的值，当前是array[i]) = true，右子节点比父节点值大不满足最大堆的条件。交换i = 4 与 rightIndex= 9 的值，即上图（c）展示的结果
3. 看（c）图，因为i=9 没有任何左右子节点，所以此次处理结束。

三、创建最大堆

以上二、保持堆的性质，具体操作目的是保证处理的结点及其所有子节点都满足最大堆的条件，但是每次操作只能保证指定结点满足条件。如果需要完整的最大堆需要对所有结点都进行以上操作，不过为了减少执行次数，堆中最下面一层所有节点需不要进行以上操作，因为最下面一下面一层节点时没有左子节点或者右右子节点的（例如：下图中8,9,10节点），所以length/2-1是按数组先后排序，最后一个父节点的索引（例如：下图中5节点），之后依次递减（例如：下图中5,4,3,2,1）。

（1）创建最大堆伪码

BUILD-MAX-HEAP(A)
1  heap-size[A] ← length[A]
2  for i ← |_length[A]/2_| downto 1
3    do MAX-HEAPIFY(A, i)

（2）创建最大堆Java实现与下图例子处理结果

    public void buildMaxHeap(int[] a, int n) {
         
          for (int i = n/2-1 ; i >= 0; i--) {
               maxHeapify(a, i, n);
          }

     }

     public static void main(String[] args) {
          int[] array = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
          System.out.println( Arrays.toString(array) );
         
          HeapSort heapSort = new HeapSort();
          heapSort.buildMaxHeap(array, array.length);
          System.out.println( Arrays.toString(array) );
     }

输入数组：[4, 1, 3, 2, 16, 9, 10, 14, 8, 7] 输出结果：[16, 14, 10, 8, 7, 9, 3, 2, 4, 1]

3. 最大堆创建过程

以上是一次对i = 5,4,3

Java 堆排序(一)