堆排序总结

本文内容来源于《漫画算法》和数据结构教材 这里提到的堆是一个二叉堆，本质上是一颗完全二叉树。堆排序只需要一个记录大小的辅助空间。 1.java实现

/** * 下沉调整 * @param arr 待调整的堆 * @param parentIndex 要下沉的父节点下标 * @param length 堆的有效大小(一般指存储堆的数组长度) */ void downAdjust(int[] arr, int parentIndex, int length) { // temp保存父节点的值，用于最后的赋值 int temp = arr[parentIndex]; int childIndex = 2 * parentIndex + 1; while (childIndex < length) { // 如果有rightChild，并且rightChild值大于leftChild值，则childIndex指向rightChild if (childIndex + 1 < length && arr[childIndex + 1] > arr[childIndex]) { childIndex++; } // 如果父节点大于子节点中的最大元素，则跳出循环，因为无需下沉 if (temp >= arr[childIndex]) break; // arr[parentIndex] = arr[childIndex]; parentIndex = childIndex; childIndex = 2 * childIndex + 1; } arr[parentIndex] = temp; } /** * 堆排序(升序) * @param arr 待调整的堆 */ void heapSort(int[] arr) { // 1.把无序数组构建成最大堆[从最后一个非叶子节点，逐个向前进行下沉调整] for (int i = (arr.length - 2) / 2; i >= 0; i--) { downAdjust(arr, i, arr.length); } System.out.println(Arrays.toString(arr)); // 2.循环删除(并非真正意义的删除，只是移动到最后)堆顶元素，移到集合尾部，调整堆产生新的堆顶 for (int i = arr.length - 1; i > 0; i--) { // 最后一个元素和第一个元素进行交换 int temp = arr[i]; arr[i] = arr[0]; arr[0] = temp; // 下沉调整 downAdjust(arr, 0, i); } } @Test public void fun1() { int[] arr = new int[] { 1, 3, 2, 6, 5, 7, 8, 9, 10, 0 }; heapSort(arr); System.out.println(Arrays.toString(arr)); }

2.C语言实现

/* * 堆排序的实现 * 数据结构(C语言版本) 严蔚敏 吴伟民 * 实现堆排序需要解决2个问题： (1)如何由一个无序序列建成一个堆？ (2)如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？ */ #include<iostream> using namespace std; /* 堆的调整 s 根节点索引 m 数组有效长度 调整为大顶堆 */ void HeapAdjust(int arr[], int s, int m) { //cout<<"m"<<m<<endl; // 保存需要调整的节点 int temp = arr[s]; for (int j = 2 * s + 1; j <= m; j = 2 * j + 1) { // 沿key较大的孩子节点向下筛选 /* cout<<"parent "<<arr[s]<<endl; cout<<"left "<<arr[j]<<endl; if(j+1<=m) cout<<"right "<<arr[j+1]<<endl; else cout<<"right"<<" is empty"<<endl; cout<<"+"<<j<<endl; */ if (j < m && arr[j] < arr[j + 1]) // j为key较大的记录的下标 ++j; //cout<<"="<<j<<endl; if (temp > arr[j]) { //cout<<temp<<"gt"<<arr[j]<<" end for loop"<<endl; break; } arr[s] = arr[j]; // 较大的节点"上浮" /* 这里省略了arr[j]=temp;这一步多余了， 只需要在最后执行这一步，将最初的s指向的元素放到最终位置即可 */ arr[j] = temp; //(1)可以在调试的时候加上这句话，方便查看最终结果 s = j; // 父节点索引指向刚调整的j位置 } arr[s] = temp; //如果循环没有发生数据交换，这一步就没必要啦，有也不会错。 //cout<<"**********************"<<endl; } void HeapSort(int arr[]) { // 1.构建堆(这个堆是一个二叉堆，本质是一颗完全二叉树) int len = 8; for (int i = len / 2 - 1; i >= 0; --i) { HeapAdjust(arr, i, len - 1); } cout << "-------------------------" << endl; // 2.调整剩余元素成为一个新的堆 for (int i = len - 1; i > 0; --i) { // 堆顶元素和当前未经排序子序列arr[0..i]中最后一个记录相互交换 int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; HeapAdjust(arr, 0, i - 1); // 将arr[0..i-1]重新调整为大顶堆 } } int main(int argc, char* argv[]) { int arr[] = { 49, 38, 65, 97, 76, 13, 27, 49 }; HeapSort(arr); int len = 8; for (int i = 0; i < len; i++) { cout << arr[i] << " "; } cout << endl; return 0; }

堆排序的练习java版[漫画算法] 堆本质上是一颗完全二叉树，用数组存储， parent,leftChild,rightChild 他们之间的数组下标的关系如下： $\{\begin{array}{l}leftChild=2\ast parent+1;\\ rightChild=2\ast parent+2;\end{array}$

---

堆排序算法步骤 1.把无序数组构建成二叉堆。 2.循环删除堆顶元素，并将该元素移到集合尾部，调整堆产生新的堆顶。 (这里的删除并非真的删除只是移动到了数组的后面相应的位置上)

时间复杂度O(nlogn) 空间复杂度O(1)

---

从宏观上看堆排序和快速排序的异同 相同点，1.堆排序和快速排序的平均时间复杂度都是O(nlogn)，并且都是不稳定排序。 不同点，1.快速排序的最坏时间复杂度是O(n^2)；而堆排序的最坏时间复杂度稳定在O(nlogn) 2.此外快排的递归和非递归方式的空间复杂度都是O(logn)， 而堆排序的空间复杂度是O(1)

在漫画算法里面，有许多的堆调整的示意图，非常有助于理解。

---

堆的定义如下：n个元素的序列$\{k_1,k_2,...,k_n,\}$当且仅当满足如下关系时，称之为堆。这里教材定义的下标是从1开始的，实际程序的下标是从0开始的，注意转换 $\{\begin{array}{l}{k}_i⩽k_{2i}\\ k_i⩽k_{2i+1}\end{array}$或$\{\begin{array}{l}{k}_i⩾k_{2i}\\ k_i⩾k_{2i+1}\end{array}$ $(i=1,2,...,\lfloor \frac{n}{2}\rfloor )$ 若将和此序列对应的一维数组（即以一维数组做此序列的存储结构）看成是一个完全二叉树，则堆的含义表名，完全二叉树中所有非终端节点的值均不大于（或不小于）其左右孩子节点的值。由此，若序列$\{k_1,k_2,...,k_n,\}$是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。 漫画算法里面的定义还是比较浅显易懂的。教材定义太复杂和吓人。