利用stl算法和迭代器编程实现堆排序
时间: 2023-12-22 22:50:01 浏览: 26
堆排序是一种基于堆的排序算法,它的时间复杂度为O(nlogn)。在STL中,我们可以使用heap算法来实现堆排序,它使用迭代器来访问容器中的元素。
下面是一个使用STL算法和迭代器实现堆排序的示例代码:
```c++
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
vector<int> arr = { 5, 3, 8, 4, 2 };
// 将数组转换为最大堆
make_heap(arr.begin(), arr.end());
// 从最大堆中取出元素并排序
sort_heap(arr.begin(), arr.end());
// 输出排序后的结果
for (auto i : arr)
cout << i << " ";
return 0;
}
```
在这个代码中,我们首先使用make_heap算法将vector转换为最大堆,然后使用sort_heap算法将堆中的元素排序。最后,我们使用循环输出排序后的结果。
相关问题
利用STL算法和迭代器编程实现堆排序
堆排序是一种利用堆的数据结构进行排序的算法,它的时间复杂度为O(nlogn)。C++的STL库中提供了make_heap()、push_heap()、pop_heap()等函数,可以方便地实现堆排序。下面是一个利用STL算法和迭代器实现堆排序的示例代码:
```
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6}; // 待排序的数组
int n = v.size();
// 构建最大堆
make_heap(v.begin(), v.end());
// 依次取出堆顶元素,并调整堆
for (int i = n - 1; i >= 0; i--)
{
// 取出堆顶元素
int tmp = v[0];
cout << tmp << " ";
// 将堆底元素移到堆顶,并调整堆
swap(v[0], v[i]);
make_heap(v.begin(), v.begin() + i);
}
return 0;
}
```
在上面的代码中,我们首先使用make_heap()函数构建了一个最大堆,然后依次取出堆顶元素,并将堆底元素移到堆顶,并调整堆,直到所有元素都被取出为止。最终的输出结果为:1 1 2 3 4 5 6 9。
用stl算法和迭代器编程实现堆排序。
堆排序是一种基于堆的排序算法,它的时间复杂度为O(nlogn)。下面是使用STL算法和迭代器实现堆排序的示例代码:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 堆排序
template<typename T>
void heapSort(vector<T>& array) {
// 将数组转换为堆
make_heap(array.begin(), array.end());
// 依次取出堆顶元素并重新调整堆
for (int i = array.size() - 1; i > 0; i--) {
// 取出堆顶元素
pop_heap(array.begin(), array.begin() + i + 1);
// 将堆顶元素放到数组末尾
swap(array[0], array[i]);
// 重新调整堆
adjust_heap(array.begin(), i);
}
}
// 调整堆
template<typename T>
void adjust_heap(T begin, int size) {
int i = 0;
int j = 2 * i + 1;
T end = begin + size;
while (j < size) {
// 找出左右子节点中较大的一个
if (j + 1 < size && *(begin + j) < *(begin + j + 1)) {
j++;
}
// 如果父节点比子节点小,则交换父子节点的值
if (*(begin + i) < *(begin + j)) {
swap(*(begin + i), *(begin + j));
i = j;
j = 2 * i + 1;
} else {
break;
}
}
}
int main() {
vector<int> array = {3, 6, 1, 8, 2, 4, 9, 5, 7};
heapSort(array);
for (auto it = array.begin(); it != array.end(); it++) {
cout << *it << " ";
}
return 0;
}
```
在上面的代码中,我们首先使用make_heap函数将数组转换为堆,然后依次取出堆顶元素并重新调整堆,直到所有元素都被取出为止。在调整堆的过程中,我们使用了自定义的adjust_heap函数,它用于将一个不符合堆定义的子树调整为堆。
运行结果为:1 2 3 4 5 6 7 8 9