泛型算法：堆算法

lexingsen

发布于 2022-02-24 18:58:56

1330

发布于 2022-02-24 18:58:56

文章被收录于专栏：乐行僧的博客

堆算法是泛型算法的一种，通过迭代器搭建泛型算法与容器联系的桥梁。

堆算法支持的四个操作：make_heap(),push_heap(),pop_heap()和sort_heap()。

注意：迭代器必须使用支持随机访问的迭代器容器类，否则不能使用该算法。

(1)make_heap

在[fisrt,last)左闭右开的区间构建一个堆。

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

int main(){
	vector<int> vec{2,1,4,7,3,8};
	cout<<"make_heap()之前：";
	for(auto i:vec){
		cout<<i<<" ";
	}
	cout<<endl;
	
	make_heap(vec.begin(),vec.end());
	cout<<"make_heap()之后："
	for(auto i:vec){
		cout<<i<<" ";
	}
	cout<<endl;
	return 0;
}

执行结果:

(2)push_heap()

push_heap()在执行前必须向支持随机访问的容器里添加进去一个元素，如vector< T >的push_back()操作。

在此之前,[first,last-1)是一个已经做好的堆，添加元素之后，堆[first,last)这个区间做堆，使用push_heap()即可。

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

int main(){
	vector<int> vec{3,5,1,2};

	make_heap(vec.bein(), vec.end());
	
	//此时vec容器元素之间的关系是一个堆
	cout<<"make_heap之后:";
	for(auto i:vec){
		cout<<i<<" ";
	}
	cout<<endl;
	vec.push_back(4);
	push_heap(vec.begin(), vec.end());
	cout<<"push_heap之后:";
	for(auto i:vec){
		cout<<i<<" ";
	}
	cout<<endl;
	return 0;
}

执行结果:

(3)pop_heap()

pop_heap()操作并不是真的将堆顶元素从容器中弹出，而是将容器最后一个元素交换到栈顶，进行shiftDown(1)操作，维持堆的性质。之后可以使用back()获取原堆顶元素，或者使用pop_bakc()操作将原堆顶元素从容器中删除。这里堆从操作可以查看这篇博客：二叉堆的实现

代码测试：

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

int main(){
	vector<int> vec{4, 1, 3, 2, 5};
	make_heap(vec.begin(), vec.end());
	cout<<"make_heap之后:";
	for(auto i:vec){
		cout<<i<<" ";
	}
	cout<<endl;
	
	pop_heap(vec.begin(), vec.end());
	cout<<"pop_heap()之后:"
	for(auto i:vec){
		cout<<i<<" ";
	}
	cout<<endl;

	cout<<"vec.back() = "<<vec.back();
	
	return 0;
}

执行结果:

(1)sort_heap

sort_heap算法可以对一个堆进行排序，排序之后也就不是一个堆了。但是如果[first,last)本身不是一个堆，这样的sort_heap是没有定义的。

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

int main(){
	vector<int> vec{4, 1, 3, 5, 2};
	make_heap(vec.begin(), vec.end());
	cout<<"make_heap之后:";
	for(auto i:vec){
		cout<<i<<" ";
	}
	cout<<endl;
	sort_heap(vec.begin(), vec.end());
	cout<<"sort_heap之后:";
	for(auto i:vec){
		cout<<i<<" ";
	}
	cout<<endl;
	return 0;
}

执行结果: