关于数据结构:堆排序-heapsort

1. 介绍

1）什么是堆？

堆是一棵 顺序存储 的齐全二叉树。

每个结点的关键字都 小于或等于 其所有子结点的关键字，这样的堆称为 小根堆。

每个结点的关键字都 大于或等于 其所有子结点的关键字，这样的堆称为 大根堆。

2）什么是堆排序？

堆排序（Heapsort）是指利用堆这种数据结构来进行排序的 抉择排序 算法。沉积是一个近似齐全二叉树的构造，并同时满足子结点的值总是小于（或者大于）它的父节点。

• 小根堆 在排序算法中用于 升序 排列；
• 大根堆 在排序算法中用于 降序 排序；

3）留神：

• 堆排序 只实用于 程序构造。
• 堆排序的均匀工夫复杂度是 O(nlongn)，最好和最坏的工夫复杂度也是 O(nlongn)。空间复杂度是 O(n)
• 堆排序是先建堆，依此输入堆顶元素（把堆顶元素换到数组前面）后调整堆。

2. 算法步骤

以 大根堆 为例，

• 创立一个大根堆
• 替换堆顶和最初一个元素，剩下的元素从新调整为 大根堆

3. 残缺代码

堆排序的全副代码如下（代码应用 Java 编写）：

// 堆排序
public void heapsort(int[] list) {build(list, list.length - 1);
    // 每调整一次堆，在数组最初就会多一个曾经排好序的数。堆中个数为 1 时，不解决
    for (int i = list.length - 1; i > 0; i--) {swap(list, 0, i);  // 排好序的数组中减少一个数
        adjust(list, 0, i - 1);
    }
}

// 建堆，自下而上建堆。先保障上面的是堆，再把后面的数退出堆中，调整为堆。public int[] build(int[] list, int end) {
    // 从最初一个父节点开始
    for (int i = (end - 1) / 2; i >= 0; i--) {adjust(list, i, end);
    }
    return list;
}

// 调整堆，从上自下调整。调整堆时，除了堆顶元素，其余的都满足堆的性质，所以从上向下把较大的元素移到下面
public int[] adjust(int[] list, int start, int end) {
    int maxIndex, left, right;
    for (int i = start; i <= (end - 1) / 2; i++) {
        maxIndex = i;
        left = 2 * i + 1;
        right = 2 * i + 2;
        if (left <= end && list[left] > list[maxIndex]) maxIndex = left;
        if (right <= end && list[right] > list[maxIndex]) maxIndex = right;
        if (maxIndex != i) {int tmp = list[i];
            list[i] = list[maxIndex];
            list[maxIndex] = tmp;
        }
    }
    return list;
}

// 替换元素。void swap(int[] list, int a, int b) {int tmp = list[a];
    list[a] = list[b];
    list[b] = tmp;
}

4. 代码阐明

以 无序序列 a = [1,3,4,5,2] 为例，通过堆排序失去的排好序的数组是 a = [1,2,3,4,5]（也能够降序排列）。从此能够看出，把堆排序看成一个处理过程，那堆排序的输出是一个无序数组（链表不能够），输入是一个有序数组。这里以大根堆为例

堆排序

一个无序序列 a = [1,3,4,5,2]，看出齐全二叉树的物理存储构造。先建成一个初始的大根堆，建堆实现之后，数组是一个大根堆 a = [5,3,4,1,2]。建堆实现之后，就须要将大根堆顺次调整为有序序列 a = [1,2,3,4,5]。

4.1 建堆

建堆的过程，就是从最初一个父节点开始，把每一棵树调整为堆的过程。

int[] build(int[] list, int end) {
    // 从最初一个父节点开始
    for (int i = (end - 1)/2; i >= 0; i--) {adjust(list, i, end);
    }
    return list;
}

首先来看一下，如果将一个无序序列建成大根堆。a = [1,3,4,5,2] 画成齐全二叉树之后，最初一个父节点是 [3]。从二叉树的最初一个父节点 [3] 开始，顺次向前遍历每一个父节点，直到根节点 [1] 为止。

从最初一个父节点开始要做什么事件呢？？

以以后父节点为根节点的二叉树，也就是 [3,5,2]，将其调整为大根堆。

最初一个父节点的下标怎么计算？？

节点下标是节点在数组中的地位，所以是从 0 到 array.length - 1。

如果一个节点下标是 i，那么它的左子叶节点下标是 2*i+1，右子叶节点下标是 2*i+2。

所以，如果数组中最初一个父节点下标为 i，最初一个元素下标是 end，那么，最初一个元素肯定是最初一个父节点的子节点。所以，就有 2*i+1 <= end 和 2*i+2 <= end，所以能够失去最初一个父节点的下标是 (end-1)/2。

建堆为什么是从最初一个父节点 (array.length-1)/2 开始向前遍历，而不是从 array.length-1 开始？

因为要保障调整堆时的参数是有意义的，没有越界产生。调整堆的代码中并没有判断下标是否非法。

建堆的程序是按档次遍历的程序遍历的，数组按从 (array.length-1)/2 到 0 拜访，是按档次遍历的形式向前遍历的。

4.2 调整堆

调整堆的过程，就是把堆顶元素放在适合的地位。

// 调整堆的起始、终止地位要是无效的
int[] adjust(int[] list, int start, int end) {
    int maxIndex, left, right;
    for (int i = start; i <= (end - 1) / 2; i++) {
        maxIndex = i;
        left = 2 * i + 1;
        right = 2 * i + 2;
        if (left <= end && list[left] > list[maxIndex]) maxIndex = left;
        if (right <= end && list[right] > list[maxIndex]) maxIndex = right;
        if (maxIndex != i) {int tmp = list[i];
            list[i] = list[maxIndex];
            list[maxIndex] = tmp;
        }
    }
    return list;
}

将哪个区间内的元素调整为堆？？

[start, end]，蕴含左右两个下标的元素。因为调整堆的代码中并没有判断数组下标的合法性，所以传入的参数要是非法的。

怎么调整？？

首先，调整的前提是，这个树满足堆的性质，除了堆顶元素。

1）找出左右子节点中的最大值，而后和堆顶元素比拟。

• 如果堆顶元素较大，则不必替换。
• 如果孩子节点较大，则将堆顶元素和较大的孩子节点替换。

2）持续调整下一个节点

调整的程序是按档次遍历的程序遍历的，数组按从 0 到 array.length-1 拜访，是按档次遍历的形式遍历的。