目录

一 基本思想1.1 什么是堆1.2 堆排序 二 例子三 时间复杂度

一 基本思想

1.1 什么是堆

堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆； 或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。堆的根结点一定是堆中的最大（小）者。

1.2 堆排序

将排序的序列构成一个大顶堆。此时，整个序列的最大值就是堆顶的根节点。将它移走（其实就是将其与堆数组的末尾元素交换），然后将剩余的 n - 1 个序列重新构成一个堆， 这样就会得到 n 个元素的次小值。如此反复执行， 便能得到一个有序序列了。

二 例子

public void Sort(int[] array) { int length = array.Length; for (int i = (length - 1) / 2; i >= 0; i--) // 把链表调整成大顶堆 { HeapAdjust(array, i, length); } for (int i = length - 1; i >= 0; i--) { Swap(array, 0, i); //将最后一个元素与根节点交换 HeapAdjust(array, 0, i);//将下标从（ 0 - i） 的元素重新组成大顶堆 } } private void HeapAdjust(int[] array, int index, int length) { int temp = array[index]; for (int i = 2 * index + 1; i < length; i = 2 * i + 1) // 获取当前结点 的 子结点 { if ((i < length - 1) && array[i] < array[i + 1]) // 如果当前结点 的 左子结点 比右子结点小， i++ { i++; // i指向数值最大的子结点 } if (temp >= array[i]) //判断 当前结点与子结点的大小 { break; //当前结点比子结点大， 不用交换当前结点与子结点，终止循环 } array[index] = array[i]; //否则， 把当前结点的数据更新为子结点的数据 index = i; //更新当前结点的坐标为该子结点的坐标 } array[index] = temp; // 退出循环， 把循环内最终找到的下标为index的结点数据更新为temp } private void Swap(int[] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; }

三 时间复杂度

堆排序的运行时间主要消耗在初始构建堆和重建堆时的反复筛选上。在构建堆的过程中，因为完全二叉树是从最底下最后边的非终端结点开始构建，将它与其孩子进行比较和互换， 对于 每个非终端结点来说， 最多进行两次比较和互换操作， 因此整个构建堆的时间复杂度是 O(n)。重建堆时， 第 i 次 取堆顶数据，并重建堆，的时间复杂度是 O(log₂ i)（因为完全二叉树第 i 个结点到根节点的距离为（log₂ i + 1）），总共需要取 n - 1 次 堆顶数据， 因此 重建的时间复杂度为 O(nlog₂ n)。总体来说， 堆排序的时间复杂度就是 O(nlog₂ n)。由于堆排序对原始数据的排序状态不敏感， 因此， 无论是最好，最差，还是平均情况的时间复杂度都是 O(nlog₂ n)。这在性能上远远好过于冒泡、简单选择、直接插入的时间复杂度O(n²)。由于初始构建堆所需的比较次数较多， 因此。它不适合待排序序列个数较少的情况。