#头条创作挑战赛#

?什么是完全二叉树？

??简单来说就是，每一层的节点都是满的；如果有节点不满，则一定是最后一层，且这层也满足从左到右依次有数据。

?怎么表示完全二叉树？

??假设有这样一个数组

• 第一个位置0就是第一层的节点
• 第二个位置1就是第二层的左
• 第三个位置2就是第二成的右
• 依次往下，每次都把节点的左右孩子填满再继续下一层

??那么这个数组就可以代表一颗完全二叉树

?数组表示的完全二叉树，找找规律吧。

??描述的文字不好理解，比较抽象，画个图简单示意下：

画的比较丑陋，简单解释一下，可以看到，每个节点都连了两个节点那么：

• 对0来说，0后面2个数就是第二层
• 对于第二层1和2来说，2后面4个数就是第三层
• 对于第三层3、4、5、6来说，6后面8个数就是第四层，因为不满8个数，所以到数组结尾都是第四层
• 那么对于节点下标来说
• 
  
• 我这个节点，扩张2倍再+1的位置就是我的左孩子
• 我这个节点，扩张2倍再+2的位置就是我的右孩子
• 我这个节点，减1位置再除以2得到的位置就是我的父节点
• 整理下
• 假设当前节点位置为i
• 左：2*i+1
• 右：2*i+2
• 父：(i-1)/2

?堆结构?

??堆就是一颗完全二叉树，堆结构要指明大根堆还是小根堆。我们用数组表示的完全二叉树，使用heapSize控制堆的大小，也就是数组中的前heapSize个数代表这个完全二叉树。

??大根堆

??每棵子树都满足头节点是最大的，或者说每个节点的值都大于或等于它的子节点的值。来个例子：

上移：heapInsert

//当前位置的值 和自己的父亲比较，谁大，谁往上跑
private void heapInsert(int[] arr,int index){
	while(arr[index] > arr[(index-1)/2]{
		swap(arr,index,(index-1)/2);
		index = (index-1)/2;
	}
}

下沉：heapify

	// 从index位置，往下看，不断的下沉
	private void heapify(int[] arr, int index, int heapSize) {
		int left = index * 2 + 1;
		// 停：较大的孩子都不再比index位置的数大；已经没孩子了
		while (left < heapSize) { // 如果有左孩子，有没有右孩子，可能有可能没有！
			// 把较大孩子的下标，给largest
			int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
			// 孩子和当前值比，谁大，就留谁
			largest = arr[largest] > arr[index] ? largest : index;
			//最大的就是自己，结束
			if (largest == index) {
				break;
			}
			// index和较大孩子，要互换
			swap(arr, largest, index);
			//继续循环
			index = largest;
			left = index * 2 + 1;
		}
	}

相关使用

??排序就是因为数据无序，假设我们原本有个大根堆，里面有些数据错误了，那怎么调整这个数据才重新变成大根堆呢？就是调用上面的“上移”和“下沉”。解释一下：

??当数据发生变化的时候，有两种情况，

1. 数据变大了
1. 本来我就是大根堆，数据从上往下是依次变小的，我这个数据变大了，肯定比下面的大
2. 所以我不需要下沉了，我上移就可以了，调用一次heapInsert
2. 数据变小了
1. 本来我是大根堆，数据从上往下依次变小，我这个数据变小了，仍然比上面的小
2. 所以我不需要上移了，我直接下沉，调用一次heapify

还有一种情况是，我不知道这个数据是变大还是变小，我只知道它变了，那我就调一次heapInsert，再调一次heapify。

??小根堆

??每棵子树都满足头节点是最小的，或者说每个节点的值都小于或等于它的子节点的值。来个例子：

小根堆也有“上移”“下沉”，和大根堆的区别只是，谁小谁上移，谁大谁下沉。

?复杂度

??堆的基本操作就是“上移”，“下沉”，这些操作只和自己的父亲或孩子比较，也就是每次比较都是相邻的两层。那么堆这个完全二叉树的高度，就决定了比较的最大次数，所以复杂度就是O(logN)的。

?堆排序

??简单梳理一下逻辑，可以肯定是大根堆的头，一定是整个大根堆最大的值，那么我只需要将这个大根堆的头，给换到数组的最后，然后减少大根堆大小，循环操作，这样就将数组从最后位置往前依次排好序了吧。

1. 先把整个数组转成大根堆
2. 这个时候heapSize就是数组的大小N，0位置的数就是大根堆的头节点最大的，那么0和N-1位置的数交换，就将最大数，换到最后面了，然后将heapSize-1，将这最后这个数从大根堆踢出去。
3. 然后0到N-1，因为0位置数据改变了，所以要保证它继续是大根堆，需要进行调整
4. 对0位置进行heapify，下沉操作，让它重新变成大根堆。
5. 这个时候0位置又变成大根堆的头节点了，0再继续和大根堆的最后一个值交换（N-2），然后heapSize再-1。
6. 循环执行逻辑，heapSize为0结束。

??代码实现

	public static void heapSort2(int[] arr) {
		// 考虑边界
		if (arr == null || arr.length < 2) {
			return;
		}
		// 使用下沉操作，将数组换成大根堆
		for (int i = arr.length - 1; i >= 0; i--) {
			heapify(arr, i, arr.length);
		}
		// 初次的heapSize
		int heapSize = arr.length;
		// 将0位置的数和最后的数交换，然后heapSize减一
		swap(arr, 0, --heapSize);
		// heapSize有值就继续，没有值说明交换完了
		while (heapSize > 0) {
			// 0位置数据产生变化了，而且是往小变化，所以下沉操作，重新变成大根堆
			heapify(arr, 0, heapSize);
			// 变成大根堆了，0位置又变成最大值了，再和最后一个数交换，然后heapSize减一
			swap(arr, 0, --heapSize);
		}
	}