堆的简介
堆排序是一种复杂度为Nlog(N)的排序算法。介绍堆排序之前先讲一讲什么是堆。这里介绍的是数据结构中的二叉堆。
二叉堆是一颗完全二叉树，一般可以直接用数组实现。它的特点：
- 父节点的键值总是大于等于（或小于等于）任何一个子节点的值。
- 每一个节点的左右子树都是一个二叉堆。
当父节点的值都大于等于子节点的值，这样的二叉堆叫做大顶堆。当父节点的值都小于等于子节点的值，叫做小顶堆。
堆排序
- 调整堆
void adjust_heap(vector<int> &v, int index, int len) {
int max = index;
int left = index*2 + 1;
int right = index*2 + 2;
if (left < len && v[left] > v[max]) max = left;
if (right < len && v[right] > v[max]) max = right;
if (max != index) {
swap(v[max], v[index]);
adjust_heap(v, max, len);
}
}
- 建造堆
void build_heap(vector<int> &v){
int len = v.size();
for (int i = (len - 2)/2; i >= 0;i--) {
adjust_heap(v, i , len);
}
}
- 堆排序
void heap_sort(vector<int> &v){
build_heap(v);
for(int i = v.size() - 1;i > 0;i--) {
swap(v[0], v[i]);
adjust_heap(v, 0, i);
}
}
- 测试
int main(){
vector<int> v = {4, 2, 7 ,11 , 8 ,10,6};
cout << "befort head_sort..." << endl;
for (auto i : v) cout << i << " ";
cout << endl;
heap_sort(v);
cout << "after heap_sort..." << endl;
for (auto i : v) cout << i << " ";
cout << endl;
return 0;
}
