# 堆排序是如何工作的？

··1796 words·4 mins·
Programming Algorithms Sorting

# 基础概念

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of node P is greater than the key of node C. A heap can be classified further as either a “max heap” or a “min heap”. In a max heap, the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node. In a min heap, the keys of parent nodes are less than or equal to those of the children and the lowest key is in the root node.

\begin{aligned} \text{idLeftChild} &= \left [ 2^i + k - 2 - (2^i - 1)\right ] + 2^{i+1} - 1\\ &= 2k - 2 + 2^{i+1} - 1 \\ &= 2^{i+1} + 2k - 4 +1 \\ &= \left (2^i + k - 2 \right )*2 + 1 \end{aligned}

# 任意普通数组的“堆化”

void max_heapify(vector<int>& arr, const int N, int i){
int largest = i;
int l = 2*i + 1;
int r = 2*i + 2;
if (l < N && arr[l] > arr[largest])
largest = l;
if (r < N && arr[r] > arr[largest])
largest = r;

// if largest val is not in parent node, we need to
// switch val of parent node and largest val
if (largest != i){
swap(arr[i], arr[largest]);
max_heapify(arr, N, largest);
}
}

void make_heap(vector<int>& arr, const int N){
for (int i = N/2 -1; i >= 0; --i){
max_heapify(arr, N, i);
}
}

# 堆排序的思想与实现

1. 把当前的无序数组变为最大堆（arr[0] 为数组最大元素）
2. 对于 i 从 n-1 到 1，
1. 交换 arr[0] 与当前数组的最后一个元素的位置 arr[i-1]，然后把堆的大小减 1
2. 把剩余的二叉树的根节点重新变为最大堆化（因为该二叉树只有根节点不满足最大堆的条件

void heap_sort(vector<int>& arr){
const int N = static_cast<int>(arr.size());
make_heap(arr, N);

for (int i = N-1; i >= 1; --i){
swap(arr[0], arr[i]);
max_heapify(arr, i, 0);
}
}

#include <bits/stdc++.h>
using namespace std;
void printArray(const vector<int>& arr){
for(auto& num: arr){
cout << num << " ";
}
cout << endl;
}

int main(){
const int N = 10;
const int rangeBegin = 0;
const int rangeEnd = 1000;

random_device rd;
mt19937 gen(rd());
uniform_int_distribution<int> distribution(rangeBegin, rangeEnd);

vector<int> arr(N, 0);
for (int i = 0; i != N; ++i){
arr[i] = distribution(gen);
}

cout << "Original array: ";
printArray(arr);

heap_sort(arr);
cout << "After heap sort: ";
printArray(arr);

return 0;
}

# References

## Related

When Does the Stability of Sorting Algorithms Matter?
··362 words·2 mins
Programming Algorithms Sorting

··1231 words·3 mins
Programming Sorting

··735 words·2 mins
Programming Algorithms Mobike