版权声明:本文源自简书tianma,转载请务必注明出处:http://www.jianshu.com/p/ad3082312012
概念
堆: 堆是具有下列性质的完全二叉树:每个节点的值都大于或等于其左右孩子(如果存在的话)的值,称为最大堆;或者每个节点的值都小于或等于其左右孩子(如果存在的话)的值,称为最小堆。
完全二叉树:
complete binary tree最大堆:
max heap
最小堆:
图片来源: 常见排序算法 - 堆排序 (Heap Sort)
堆排序:利用堆(这里使用最大堆)进行排序的方法。其基本思想是:将待排序的序列构造成一个最大堆,此时待排序序列的最大值就是堆顶的根节点,将其移走(其实就是将其与待排序序列的最后一个元素进行交换,此时待排序序列最后一个元素就是最大值),然后将剩余的序列重新构造成一个堆,如此反复,直到待排序序列只有一个元素为止,则排序完成。
性质
已知arr[0...n-1]是长度为n的最大堆数组,下标从0开始,那么对于下标为i的节点I,有:
(1). 如果I的左孩子存在的话,那么I的左孩子节点的下标为 left(i) = 2*i+1;
(2). 如果I的右孩子存在的话,那么I的右孩子节点的下标为 right(i) = 2*i+2;
(3). 如果I双亲节点存在的话,那么I的双亲节点的下标为 parent(i) = (i-1)/2; (向下取整)
基本操作
- 构建最大堆 buildMaxHeap(int[] arr):将待排序序列arr构建成最大堆;
- 调整最大堆 adjustHeap(int arr[], int begin, int end): 已知arr[begin]的左子树和右子树都满足最大堆,那么调节节点arr[begin],将以arr[begin]为根节点的二叉树调整为最大堆。
对于堆排序,最重要的就是构建最大堆和调整最大堆,其实构造初始堆事实上也是调整堆的过程,只不过构造初始堆是对所有的非叶节点都进行调整。
Java实现
// 定义接口
interface Sorter {
/**
* 将数组按升序排序
*/
int[] sort(int[] arr);
/**
* 交换数组arr中的第i个位置和第j个位置的关键字
*/
default void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
// 堆排序
class HeapSorter implements Sorter {
@Override
public int[] sort(int[] arr) {
heapSort(arr);
return arr;
}
private void heapSort(int[] arr) {
buildMaxHeap(arr); // 构建最大堆
// 将最大堆堆顶元素与数组末尾元素交换,并将前n-1序列重新构造成最大堆,重复n-1次
for (int i = arr.length - 1; i >= 1; i--) {
swap(arr, 0, i); // 将堆顶元素和当前未经排序的子序列的最后一个元素进行交换
adjustHeap(arr, 0, i - 1); // 将arr[0...i-1](前i个元素)重新调整为最大堆
}
}
/**
* 将指定数组arr构建成最大堆
*/
private void buildMaxHeap(int[] arr) {
int len = arr.length;
// 从最后一个非叶子节点往前遍历,将当前序列构成最大堆
for (int i = len / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, len - 1);
}
}
/**
* 假定arr[begin]的左子树和右子树均满足最大堆,那么调节节点arr[begin],将以arr[begin]为根节点的二叉树调整为最大堆。
*/
private void adjustHeap(int[] arr, int begin, int end) {
int tmp = arr[begin];
int j;
for (j = 2 * begin + 1; j <= end; j = 2 * j + 1) {
// j=2*begin+1表示j对应二叉树节点的左孩子
if (j + 1 <= end && arr[j] < arr[j + 1]) {
// 如果当前节点的右孩子存在且左孩子的值小于右孩子
j++; // j为左右孩子较大记录的下标
}
if (tmp >= arr[j]) // tmp的值已经大于arr[j],则调整完毕,跳出循环
break;
arr[begin] = arr[j]; // 当前根节点并未均大于左右节点(如果有的话),重新给当前根节点赋值
begin = j; // begin指向新的可能需要进行最大堆调整的子树的根节点
}
arr[begin] = tmp;
}
}
堆排序其实也是一种选择排序,是一种树形选择排序。在简单选择排序中,从arr[0...n-1]中选择最小(或最大)记录,需要比较n-1次,然后再从剩下arr[1...n-1]的n-1个元素中选择最小(或最大)记录,需要比较n-2次。然而事实上这n-2次比较中,有许多已经在前一趟n-1次的比较中做过了;而树形选择排序恰好利用树形的特点保存了部分前面的比较结果,因此可以减少比较次数,提高算法效率。
复杂度
时间复杂度:
对于n个关键字序列,每个节点需比较log2(n)次,因此其时间复杂度为O(nlogn)。
由于堆排序对原始记录的排序状态并不敏感,所以它的最好、最坏、平均时间复杂度均为O(nlogn)
由于初始构建堆所需要的比较次数较多,所以堆排序不适合待排序序列个数少的情况。
空间复杂度:
最好情况=平均情况=最坏情况=O(1)
网友评论