【C】堆的应用1 -- 堆排序

  之前学习了堆，堆的一棵以顺序结构存储的完全二叉树，堆本身又氛围大根堆和小根堆，假设以大根堆为例，由于堆顶部元素是一棵二叉树里面最大的元素，所以如果每次都取堆顶的元素，那么取出的元素就是一个降序排列的序列。至此，我们发现了一个堆的特别重要的一个应用，就是堆排序。

---

目录

1  问题解析

2  算法分析

3  代码 

4  时空复杂度分析

（1） 时间复杂度

（2） 空间复杂度

---

1  问题解析

  堆排序顾名思义就是用堆结构来实现对一个数组的排序，但是在排序过程中是不能使用堆这个数据结构的。如：有一个数组 a[] = {2, 4, 10, 9,  2,  3}，通过堆排序这个排序算法之后，数组 a 里面的数据变为了 a[] = {2, 2, 3, 4, 9, 10} 升序排列；或者是 a[]  = {10, 9, 4, 3, 2, 2} 降序排列。

---

2  算法分析

  该算法共分为两步：

  1） 首先对于给定的一个数组，数组里面的数据都是乱序的，既然是堆排序，我们就需要先让该数组里面的数据变成一个堆，将数组中的数据变成一个堆的算法为(这里是建大堆，建小队逻辑类似)：
  这里利用的是向下调整算法，因为向下调整算法的时间效率是比向上调整算法的时间效率高的（上一篇文章有所讲解），而向下调整算法又需要其左右子树各自都是一个堆，所以首先选择最后一个节点作为孩子节点，让其父亲向下调整，这样最后一棵子树就变成了一个堆，然后再以当前孩子节点的上一个节点作为下一个孩子节点，让其父亲向下调整，直至所有的子树都被调整为了一个堆。该过程如图所示：

 

其本质就是从最小的一个子树建堆，然后使子树规模依次扩大，最后扩大为整棵树。

  2）数组建完堆之后，由于堆顶数据总是最大的，所以我们选择让堆顶数据和最后一个节点的数据进行交换，这样最后一个数据就是有序的，然后让交换后的堆顶数据再向下建堆，但是注意这次建堆的范围应是 n - 1 个数据（n 为数组中数据的个数）；那么当前我们执行完 n - 1 次该操作之后，最大的 n - 1 个数据就会被升序的放到后 n - 1 个位置，所以就实现了升序排列。该算法如图所示：

  通过理解该算法，如果要排升序的话，那么应该建大堆；排降序的话，应该建小堆。

---

3  代码 

//升序的话，建大堆；降序的话，建小堆
//这里升序排列
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}void AdjustDown(int* arr, int parent, int n)
{int child = 2 * parent + 1;while (child < n){if (arr[child + 1] > arr[child] && child + 1 < n){child++;}if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = 2 * parent + 1;}else{break;}}
}//Heap是堆的意思，Sort是排序的意思
void HeapSort(int* arr, int n)
{//先用所给的数组向下调整建一个堆for (int i = (n-1-1)/2;i >= 0;i--){AdjustDown(arr, i, n);}//然后每次交换堆顶元素和最后一个元素，让剩余元素建大堆int end = n;while (end > 0){//先交换Swap(&arr[0], &arr[--end]);//然后剩下元素建大堆AdjustDown(arr, 0, end);}
}

测试用例：

void Test()
{int arr[] = { 10, 9, 2, 4, 6, 11, 56, 20, 15, 19};int n = sizeof(arr) / sizeof(arr[0]);HeapSort(arr, n);for (int i = 0; i < n; i++){printf("%d ", arr[i]);}
}int main()
{Test();return 0;
}

---

4  时空复杂度分析

（1） 时间复杂度

  在上一篇文章中，我们分析了向下调整算法的时间复杂度为 O(logn) 的，而在堆排序里面共有两次循环，第一次循环会执行 n/2 - 1 次，第二次循环会执行 n 次，而这两次循环里面都嵌套了向下调整算法，所以时间复杂度为 O( (n/2 - 1)*logn + nlogn)，去除常数项和低阶项，堆排序时间复杂度就是 O(nlogn)的。

（2） 空间复杂度

  由于堆排序算法仅用了几个变量，并为额外开辟空间，所以空间复杂度为 O(1)。