java实现堆排序以及时间复杂度的分析

完全二叉树：从上到下，从左到右，每层的节点都是满的，最下边一层所有的节点都是连续集中在最左边。

二叉树的特点就是左子节点是父节点索引值的2倍加一，右子节点是父节点索引值的2倍加二

堆分为两种：大顶堆和小顶堆

        大顶堆：在完全二叉树基础上，每个节点的值都大于或等于其左右子节点的值

        小顶堆：在完全二叉树基础上，每个节点的值都大于或等于其左右子节点的值

堆排序就是根据先构建好的大顶堆或小顶堆进行排序的。

怎么构建大顶堆：

        假如一个数组是：int[] arr= {3,5,7,9,1,2,4,6,8,11,10};它的完全二叉树形状如下图所示：

红色数字的是节点在数组中的索引值，它们之间的关系就是左子节点是父节点索引值的2倍加一，右子节点是父节点索引值的2倍加二

 我们想把它构建成大顶堆就从二叉树最下面一层开始也就是从最后一个数组开始，先比较左右子树，找到最大的一个，用最大的和父节点进行比较如果子节点大就进行交换，交换结束后再比较此层左边的左右和父子节点进行交换。也就是从最下一层开始，从右到左开始比较，此层比较完进入上一层再从右到左开始比较以此循环。当到达上一层时会有一个问题就是如果换下来的父节点比子节点小我们还需要往下进行交换，我们就需要对它进行维护。

上面数组的例子按顺序构建的大顶堆如下图所示：

 构建好的大顶堆的根节点总是最大的，我们根据这个特点进行排序。

我们把根节点和树的最后一个叶子节点进行交换即让数组的第一个数和最后一个数交换，交换后让最后一个数保持位置不再变化，我们再让其他节点再进行维护大顶堆，因为此时根节点是比子节点小的，重复以上操作直到需要根节点和他本身进行交换时排序完成

排序流程图如下：

代码如下：

public class heapsort {
	public static void main(String[] args) {
		int[] arr= {3,5,7,9,1,2,4,6,8,11,10};
		for(int p=arr.length-1;p>=0;p--) {
			adjustheap(arr,p,arr.length);
		}
		heapsort(arr);
		System.out.println(Arrays.toString(arr));
	}
 
	public static void heapsort(int[] arr) {
		for(int i=arr.length-1;i>=0;i--) {
			int temp=arr[i];
			arr[i]=arr[0];
			arr[0]=temp;
			adjustheap(arr, 0, i);
		}
		
	}
 
	public static void adjustheap(int[] arr, int p, int length) {
		int temp=arr[p];
		int left=p*2+1;
		while(left<length) {
			if(left+1<length&&arr[left]<arr[left+1]) {
				left++;
			}
			if(temp>arr[left]) {
				break;
			}
			arr[p]=arr[left];
			p=left;
			left=left*2+1;
			
		}
		arr[p]=temp;
	}

 输出结果如下：

 时间复杂度：构建大顶堆的时间复杂度是O（nlogn）,n是main方法里的for循环，logn是构建大顶堆的方法的时间复杂度，排序的时间复杂度也是O（nlogn），所以堆排序的时间复杂度是O（nlogn）+O（nlogn）,也就是O（logn）