首页 > STL编程 > STL堆排序详解

STL堆排序详解

           在STL中,有很多的排序函数模板供我们调用,省去我们自己编写一些排序过程的麻烦。本文是一篇关于STL中堆排序的一个介绍。

    本文涉及的几个函数如下:make_heap(), push_heap(), pop_heap(), is_heap(), sort_heap()。其中make_heap()用于构建一个堆(如果你对“堆”这个数据结构不了解,请先去学习有关“堆”数据结构的知识再来查看本文)
SGI STL中对make_heap()的声明如下:

template <class RandomAccessIterator>
void make_heap(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
void make_heap(RandomAccessIterator first, RandomAccessIterator last,
StrictWeakOrdering comp);

就是说make_heap()有两个重载版本,事实上都差不多,都是指定一个需要处理的区间,第二个版本只不过是自己定义一个比较准则而已。默认(第一种)是以operator<来作为比较准则的。

SGI STL中对push_heap()的声明如下:

template <class RandomAccessIterator>
void push_heap(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
void push_heap(RandomAccessIterator first, RandomAccessIterator last,
StrictWeakOrdering comp);

形式和make_heap()差不多,pop_heap()用于将指定区间的最后一个元素加入堆中并使整个区间成为一个新的堆。注意前提是最后一个元素除外的所有元素已经构成一个堆。

SGI STL中对pop_heap()的声明如下:

template <class RandomAccessIterator>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last, trictWeakOrdering comp);

和push_heap()相反,pop_heap()用于弹出堆中的第一个元素,并把它放到区间的最后一个位置,然后重新将前面的元素构建成一个堆。

SGI STL中对is_heap()的声明如下:

template <class RandomAccessIterator>
bool is_heap(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
inline bool is_heap(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp)

is_heap()用于判断一个区间是否是一个堆。这个函数在push_heap()之前用一下可以确保区间已经构成一个堆。

下面来看一个例子:

//Coded By 代码疯子
#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
using namespace std;

void print(int elem)
{
	cout << elem << ' ';
}

int main()
{
	vector<int> coll;
	int n;
	
	while(cin >> n && n)
	{
		coll.push_back(n);
	}
	
	make_heap(coll.begin(), coll.end());
	cout << "After make_heap()" << endl;
	for_each(coll.begin(), coll.end(), print);
	cout << endl;
	
	cin >> n;
	coll.push_back(n);
	push_heap(coll.begin(), coll.end());
	
	cout << "After push_heap()" << endl;
	for_each(coll.begin(), coll.end(), print);
	cout << endl;
	
	pop_heap(coll.begin(), coll.end());
	cout << "After pop_heap()" << endl;
	for_each(coll.begin(), coll.end(), print);
	cout << endl;
	
	cout << "coll.back() : " << coll.back() << endl;
	coll.pop_back();
	
	sort_heap(coll.begin(), coll.end());
	cout << "After sort_heap()" << endl;
	for_each(coll.begin(), coll.end(), print);
	cout << endl;
	
	return 0;
}

程序的运行测试截图如下:

STL heap sort


觉得文章还不错?点击此处对作者进行打赏!


本文地址: 程序人生 >> STL堆排序详解
作者:代码疯子(Wins0n) 本站内容如无声明均属原创,转载请保留作者信息与原文链接,谢谢!


更多



  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.