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

1）什么是堆？

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

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

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

2）什么是堆排序？

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

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

3）留神：

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

以大根堆为例，

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

堆排序的全副代码如下（代码应用 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;
}

以无序序列 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]。

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

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 拜访，是按档次遍历的形式向前遍历的。

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

// 调整堆的起始、终止地位要是无效的
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 拜访，是按档次遍历的形式遍历的。

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

1. 介绍

2. 算法步骤

3. 残缺代码

4. 代码阐明

4.1 建堆

4.2 调整堆