[数据结构与算法]排序算法五-堆排序

此代码生成从小到大的顺序，故先构造一棵大堆树，然后将根节点与层序遍历最后一个节点或最后一个下标交换，遍历这个过程直到最后一个节点

//向上调整
	//变成大顶堆
	public static void heapInsert(int[] arr, int index) {
		while (arr[index] > arr[(index - 1) / 2]) {
			swap(arr, index, (index - 1) /2);
			index = (index - 1)/2 ;
		}
	}
//向下调整
	public static void heapify(int[] arr, int index, int size) {
		//左节点下标
		int left = index * 2 + 1;
		while (left < size) {
			//找出左右节点值最大的那个
			int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
			//如果左右节点最大值比父节点大则交换，否则不交换
			largest = arr[largest] > arr[index] ? largest : index;
			if (largest == index) {
				break;
			}

			swap(arr, largest, index);
			//以最大值的节点作为头节点
			index = largest;
			left = index * 2 + 1;
		}
	}

	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}