数据结构之堆排序

---

---

堆排序

版本一

1. 基于已有数组建堆
2. 取堆顶元素并删除堆顶元素重新建大根堆，完成排序版本。
   

图文理解

版本二

前提：必须提供有现成的数据结构堆

数组建堆，首尾交换，交换后的堆尾数据从堆中删掉，将堆顶数据向下调整选出次大的数据。

向下调整建堆

1. 先把每棵子树通过向下调整算法建成大根堆；
2. 整体建成大根堆结构。
   

	for (int i = (n - 1 - 1) / 2;i >= 0;i--){AdjustDown(arr, i, n);}

void AdjustDown(HPDataType* arr, int parent, int n)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && arr[child] < arr[child + 1]){child++;}//>建小堆//<建大堆if (arr[parent] < arr[child]){Swap(&arr[parent], &arr[child]);parent = child;child = parent * 2 + 1;}else {break;}}
}

向上调整建堆

1. 堆顶元素开始建堆；
2. 通过将每一个结点进行建大根堆，最后整体就是大根堆结构。

通过顺序结构二叉树文章可知，向下调整算法的时间复杂度优于向上调整算法，因此更推荐用向下调整建堆。

	for (int i = 0;i < n;i++){AdjustUp(arr, i);}

//向上调整
void AdjustUp(HPDataType* arr, int child)
{int parent = (child - 1) / 2;while (child > 0){//>:大堆//<:小堆if (arr[child] > arr[parent]){//交换Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else {break;}}
}

排升/降序

排成升序结构，建大根堆；
排成降序结构，建小根堆。

升序

	int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDown(arr, 0, end);end--;}

注:当前是大根堆结构

1. 将堆顶数据与末端数据交换；
2. 重新建成大根堆结构，保证下次取到的堆顶数据依然是最大值；
3. 最后数据将会排成升序结构。

那么，降序结构原理也类似上图所示。

---

---