各种排序算法总结( 二 ) _算法

每个结点的左子树和右子树都是一个二叉堆

当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。一般二叉树简称为堆。
【各种排序算法总结】堆的存储
一般都是数组来存储堆，i结点的父结点下标就为(i – 1) / 2 。它的左右子结点下标分别为2 * i + 1和2 * i + 2 。如第0个结点左右子结点下标分别为1和2 。存储结构如图所示：

文章插图
堆结构.png
堆排序原理
堆排序的时间复杂度为O(nlogn)

算法原理（以最大堆为例）
先将初始数据R[1..n]建成一个最大堆，此堆为初始的无序区
再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key
由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。
重复2、3步骤，直到无序区只有一个元素为止。
c++代码实现

/** * 将数组arr构建大根堆 * @param arr 待调整的数组 * @param i 待调整的数组元素的下标 * @param len 数组的长度 */void heap_adjust(int arr[], int i, int len){ int child; int temp; for (; 2 * i + 1 < len; i = child) { child = 2 * i + 1; // 子结点的位置 = 2 * 父结点的位置 + 1 // 得到子结点中键值较大的结点 if (child < len - 1 && arr[child + 1] > arr[child]) child ++; // 如果较大的子结点大于父结点那么把较大的子结点往上移动，替换它的父结点 if (arr[i] < arr[child]) { temp = arr[i]; arr[i] = arr[child]; arr[child] = temp; } else break; }}/** * 堆排序算法 */void heap_sort(int arr[], int len){ int i; // 调整序列的前半部分元素，调整完之后第一个元素是序列的最大的元素 for (int i = len / 2 - 1; i >= 0; i--) { heap_adjust(arr, i, len); } for (i = len - 1; i > 0; i--) { // 将第1个元素与当前最后一个元素交换，保证当前的最后一个位置的元素都是现在的这个序列中最大的 int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // 不断缩小调整heap的范围，每一次调整完毕保证第一个元素是当前序列的最大值 heap_adjust(arr, 0, i); }}