STL算法-17堆（排序）算法

堆（排序）算法

1. make_heap()

   ：建堆

2. push_heap()

   ：插入堆元素

3. pop_heap()

   ：删除堆元素

4. sort_heap()

   ：堆排序重排成普通排序

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	vector<int> ivec;

	for (int i = 3; i <= 7; ++i)
		ivec.push_back(i);
	for (int i = 5; i <= 9; ++i)
		ivec.push_back(i);
	for (int i = 1; i <= 4; ++i)
		ivec.push_back(i);

	cout << "ivec原始資料：" << endl;
	for (vector<int>::iterator iter = ivec.begin();
		iter != ivec.end(); ++iter)
		cout << *iter << ' ';
	cout << endl;

	//資料在向量中，隻是将其排列成堆
	make_heap(ivec.begin(), ivec.end());
	cout << "ivec按堆排序：" << endl;
	for (vector<int>::iterator iter = ivec.begin();
		iter != ivec.end(); ++iter)
		cout << *iter << ' ';
	cout << endl;

	pop_heap(ivec.begin(), ivec.end());
	cout << "取出ivec最大值放到ivec末尾，其餘數重建立堆：" << endl;
	for (vector<int>::iterator iter = ivec.begin();
		iter != ivec.end(); ++iter)
		cout << *iter << ' ';
	cout << endl;

	ivec.pop_back();
	cout << "删除最大ivec資料：" << endl;
	for (vector<int>::iterator iter = ivec.begin();
		iter != ivec.end(); ++iter)
		cout << *iter << ' ';
	cout << endl;

	// 往堆中新增資料，必須向将資料加入ivec末尾（重點：資料加入vector，加入至vector末尾）
	ivec.push_back(17);
	cout << "在ivec中新增資料：" << endl;
	for (vector<int>::iterator iter = ivec.begin();
		iter != ivec.end(); ++iter)
		cout << *iter << ' ';
	cout << endl;
	
	push_heap(ivec.begin(), ivec.end());
	cout << "新堆資料：" << endl;
	for (vector<int>::iterator iter = ivec.begin();
		iter != ivec.end(); ++iter)
		cout << *iter << ' ';
	cout << endl;

	// 将堆排序變成普通排序
	sort_heap(ivec.begin(), ivec.end());
	cout << "堆排序變成普通排序：" << endl;
	for (vector<int>::iterator iter = ivec.begin();
		iter != ivec.end(); ++iter)
		cout << *iter << ' ';
	cout << endl;

	return 0;
}