InTheBloodHorse

数据结构与算法(5) 堆排序

字数统计: 197阅读时长: 1 min
2018/09/26 Share

之前讲到过二叉堆,二叉堆可以实现优先队列和堆排序,今天就来讲讲堆排序。
其实只要理解了二叉堆,堆排序就很简单了。
无论是最大堆最小堆,堆顶元素肯定是最大|最小的,所以我们每次pop出堆顶的元素,记录。删除堆顶的元素,二叉堆会自动维护,所以堆顶的元素又是当前最大|最小的。
加上之前的代码就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
case 4:{
if(is_small_heap == false){
cout << "先生成最小堆" << endl;
break;
}
vector<int>ans;
int length = v.size();
for(int i=0;i<length;i++){
ans.push_back(v[0]);
delete_node(0);
}
for(int i=0;i<ans.size();i++){
cout << ans[i] << " ";
}
cout << endl;
break;
}

CATALOG