算法-堆排序

发表于 2018-01-09 更新于 2020-11-10 分类于算法

学习堆排序

堆排序是内部排序中选择排序的一种。堆排序是一种树形选择排序，是对选择排序的有效改进。

堆是一种具有n个元素的序列，当且仅当满足 ki<=k2i, ki<= k2i+1，或者反过来。
若以一维数组存储一个堆，则堆对应一棵完全二叉树，且所有非叶结点的值均不大于(或不小于)其子女的值，根结点（堆顶元素）的值是最小(或最大)的。

初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树（一维数组存储二叉树），调整它们的存储序，使之成为一个堆，将堆顶元素输出，得到n 个元素中最小(或最大)的元素，这时堆的根节点的数最小（或者最大）。
然后对前面(n-1)个元素重新调整使之成为堆，输出堆顶元素，得到n 个元素中次小(或次大的元素。
依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。称这个过程为堆排序。

调整小堆顶的方法

1）设有m 个元素的堆，输出堆顶元素后，剩下m-1 个元素。将堆底元素送入堆顶（（最后一个元素与堆顶进行交换），堆被破坏，其原因仅是根结点不满足堆的性质。

2）将根结点与左、右子树中较小元素的进行交换。

3）若与左子树交换：如果左子树堆被破坏，即左子树的根结点不满足堆的性质，则重复方法（2）.

4）若与右子树交换，如果右子树堆被破坏，即右子树的根结点不满足堆的性质。则重复方法（2）.

5）继续对不满足堆性质的子树进行上述交换操作，直到叶子结点，堆被建成。

建堆方法：对初始序列建堆的过程，就是一个反复进行筛选的过程。

1）n 个结点的完全二叉树，则最后一个结点是第个结点的子树。

2）筛选从第个结点为根的子树开始，该子树成为堆。

3）之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。

算法思想

空间复杂度

因为堆排序是就地排序，空间复杂度为常数：O(1)

时间复杂度

堆排序的时间复杂度，主要在初始化堆过程和每次选取最大数后重新建堆的过程；

初始化建堆过程时间：O(n)

推算过程：

首先要理解怎么计算这个堆化过程所消耗的时间，可以直接画图去理解；

假设高度为k，则从倒数第二层右边的节点开始，这一层的节点都要执行子节点比较然后交换（如果顺序是对的就不用交换）；倒数第三层呢，则会选择其子节点进行比较和交换，如果没交换就可以不用再执行下去了。如果交换了，那么又要选择一支子树进行比较和交换；

那么总的时间计算为：s = 2^( i - 1 ) * ( k - i )；其中 i 表示第几层，2^( i - 1) 表示该层上有多少个元素，( k - i) 表示子树上要比较的次数，如果在最差的条件下，就是比较次数后还要交换；因为这个是常数，所以提出来后可以忽略；

S = 2^(k-2) * 1 + 2^(k-3)2…..+2(k-2)+2^(0)*(k-1) ===> 因为叶子层不用交换，所以i从 k-1 开始到 1；
这个等式求解，我想高中已经会了：等式左右乘上2，然后和原来的等式相减，就变成了：
S = 2^(k - 1) + 2^(k - 2) + 2^(k - 3) ….. + 2 - (k-1)
除最后一项外，就是一个等比数列了，直接用求和公式：S = { a1[ 1- (q^n) ] } / (1-q)；
S = 2^k -k -1；又因为k为完全二叉树的深度，所以 (2^k) <= n < (2^k -1 )，总之可以认为：k = logn （实际计算得到应该是 log(n+1) < k <= logn ）;
综上所述得到：S = n - longn -1，所以时间复杂度为：O(n)
更改堆元素后重建堆时间：O(nlogn)
推算过程：
1、循环 n -1 次，每次都是从根节点往下循环查找，所以每一次时间是 logn，总时间：logn(n-1) = nlogn - logn ；
综上所述：堆排序的时间复杂度为：O(nlogn)

算法实现思想

堆排序的大概步骤如下:

构建最大堆。
选择顶，并与第0位置元素交换
由于步骤2的的交换可能破环了最大堆的性质，第0不再是最大元素，需要调用maxHeap调整堆(沉降法)，如果需要重复步骤2

java实现

public static void heapSort(int[] array) {  
    if (array == null || array.length <= 1) {  
        return;  
    }  
  
    buildMaxHeap(array);  
  
    for (int i = array.length - 1; i >= 1; i--) {  
    	ArrayUtils.exchangeElements(array, 0, i);  

    	maxHeap(array, i, 0);  
    }  
}  
  
private static void buildMaxHeap(int[] array) {  
	if (array == null || array.length <= 1) {  
		return;  
	}  

	int half = array.length / 2;  
	for (int i = half; i >= 0; i--) {  
		maxHeap(array, array.length, i);  
	}  
}
private static void maxHeap(int[] array, int heapSize, int index) {  
	int left = index * 2 + 1;  
	int right = index * 2 + 2;  

	int largest = index;  
	if (left < heapSize && array[left] > array[index]) {  
		largest = left;  
	}  

	if (right < heapSize && array[right] > array[largest]) {  
		largest = right;  
	}  

	if (index != largest) {  
		ArrayUtils.exchangeElements(array, index, largest);  

		maxHeap(array, heapSize, largest);  
	}  
}  
public static void exchangeElements(int[] array, int index1, int index2) {  
	int temp = array[index1];  
	array[index1] = array[index2];  
	array[index2] = temp;  
}

个人小站