泛型算法：堆算法

堆算法是泛型算法的一種，通過疊代器搭建泛型算法與容器聯系的橋梁。

堆算法支援的四個操作：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;
}           

複制

執行結果: