C++基础：模拟实现priority_queue(堆)，详细介绍仿函数

引言

        手把手带你模拟实现堆：priority_queue。详细介绍仿函数，感受仿函数的魅力

一、模拟实现priority_queue

优先级队列：priority_queue，底层的数据结构是堆。

这里实现的是大根堆，小根堆把比较符号改一下即可。

用vector做适配器来实现

先写出基本框架：

	template<class T, class container = vector<T>>class priority_queue{public://函数private:container _con;  };

两个核心操作：向上调整算法，向下调整算法

（看代码理解，很简单）

	template<class T, class container = vector<T>>class priority_queue{public://函数private:void adjust_down(size_t parent) //核心，向下调整算法{size_t child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() - 1 && _con[child] < _con[child + 1]) child++;if (_con[parent] < _con[child]){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}void adjust_up(size_t child) //核心，向上调整算法{size_t parent = (child - 1) / 2;while (child > 0){if (_con[parent] < _con[child]){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}private:container _con;  };

插入push()，删除pop()，返回堆顶元素top()，判空empty()，堆中元素个数size()

	template<class T, class container = vector<T>>class priority_queue{public:void push(const T& x) //插入，入堆{_con.push_back(x);adjust_up(_con.size() - 1);}void pop() //删除堆顶元素{swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T& top()// 返回堆顶元素{return _con[0];}bool empty() const //判空{return _con.empty();}size_t size() const //返回元素个数{return _con.size();}private:void adjust_down(size_t parent) //核心，向下调整算法{size_t child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() - 1 && _con[child] < _con[child + 1]) child++;if (_con[parent] < _con[child]){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}void adjust_up(size_t child) //核心，向上调整算法{size_t parent = (child - 1) / 2;while (child > 0){if (_con[parent] < _con[child]){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}private:container _con;  };

用迭代器区间构造堆

注意：自己写了构造函数，编译器不会生成默认构造函数了，所以要强制编译器自己生成默认构造函数。

	template<class T, class container = vector<T>>class priority_queue{public:priority_queue() = default;  //因为下面写了个构造函数//所以要强制函数生成默认构造template<class InputIterator>priority_queue(InputIterator first, InputIterator last) //用迭代器构造堆的构造函数:_con(first, last){//向下调整建堆O(N), 向上调整算法(N*lnN)for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){adjust_down(i);}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T& top(){return _con[0];}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}private:void adjust_down(size_t parent) //核心，向下调整算法{size_t child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() - 1 && _con[child] < _con[child + 1]) child++;if (_con[parent] < _con[child]){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}void adjust_up(size_t child) //核心，向上调整算法{size_t parent = (child - 1) / 2;while (child > 0){if (_con[parent] < _con[child]){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}private:container _con;  };

 测试来看一下：

void test02()
{vector<int> v = { 1, 2, 3,4, 5, 6 };stl::priority_queue<int> pq(v.begin(), v.end());while (!pq.empty()){cout << pq.top() << " ";pq.pop();}
}
int main()
{test02();return 0;
}

符合大根堆。

二、仿函数

什么是仿函数？

        仿函数（Functor）也被叫做函数对象（Function Object），它是一种行为类似函数的对象。要创建仿函数，只需定义一个类或结构体，并在其中重载operator()。当这个类的实例像函数那样被调用时，实际执行的就是重载后的operator()。

看这段话可能不能很清楚，下面一步一步来引进仿函数。

正常实现一个比较小于的函数：

bool lessFunc(int x, int y)
{return x < y;
}int main()
{cout << lessFunc(1, 2);return 0;
}

用仿函数来实现一个比较小于的函数：

bool lessFunc(int x, int y)
{return x < y;
}//仿函数：
template<class T>
class Less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};int main()
{cout << lessFunc(1, 2) << endl;Less<int> LessF;cout << LessF(1, 2) << endl;//仿函数的本质：cout << LessF.operator()(1, 2) << endl;return 0;
}

可以看到，仿函数是定义一个类或结构体，并在其中重载operator()。

仿函数的设计可以替代函数指针。

作用一：

用仿函数对冒泡排序进行改进一下：

// < 升序
// > 降序
template<class T, class Compare>
void BubbleSort(T* a, int n, Compare com)// com作为参数，需要传递一个对象过来
{int exchange = 0;for (int i = 0; i < n; i++){for (int j = 0; j < n - i - 1; j++){//if (a[j + 1] < a[j])if(com(a[j + 1], a[j])) //传函数来控制比较逻辑{exchange = 1;swap(a[j], a[j + 1]);}}if (exchange == 0){break;}}
}

//仿函数：
template<class T>
class Less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};template<class T>
class Greater
{
public:bool operator()(const T& x, const T& y){return x > y;}
};

 实际应用：

int main()
{//cout << lessFunc(1, 2) << endl;//Less<int> LessF;//cout << LessF(1, 2) << endl;////仿函数的本质：//cout << LessF.operator()(1, 2) << endl;int a[] = { 1 ,6, 1, 5, 4, 3, 10};BubbleSort(a, 7, Less<int>()); //控制升序for (auto& e : a){cout << e << " ";}cout << endl;BubbleSort(a, 7, Greater<int>()); //控制降序for (auto& e : a){cout << e << " ";}cout << endl;return 0;
}

使用仿函数控制priority_queue的大根堆和小根堆

（将看到函数指针的不行之处）

        要控制是大根堆还是小根堆，需要调整算法的比较逻辑。

仿函数：

//仿函数：
template<class T>
class Less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};template<class T>
class Greater
{
public:bool operator()(const T& x, const T& y){return x > y;}
};

增加一个参数： 

namespace bit
{//增加一个类型参数：template<class T, class Container = vector<T>, class Compare = Less<T>>class priority_queue{private:Container _con;    Compare com;  //传比较函数};
}

namespace bit
{template<class T, class Container = vector<T>, class Compare = Less<T>>class priority_queue{public://函数。。。private:void adjust_up(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){//if (_con[child] > _con[parent])//if (_con[parent] < _con[child])if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjust_down(int parent){Compare com;size_t child = parent * 2 + 1;while (child < _con.size()){// 选出大的那个孩子if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))++child;if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}private:Container _con;};
}

核心算法：

template<class T, class container = vector<T>, class Compare = Less<T> > //模拟是小根堆class priority_queue{public://函数private:		void adjust_down(size_t parent) //核心，向下调整算法{size_t child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() - 1 && com(_con[parent], _con[child])) child++;//if (_con[parent] < _con[child])if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}void adjust_up(size_t child) //核心，向上调整算法{size_t parent = (child - 1) / 2;while (child > 0){//if (_con[parent] < _con[child])if(com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}private:container _con;  Compare com;};

来试一下，建一个小根堆：

int main()
{//bit::priority_queue<int> pq;stl::priority_queue<int, vector<int>, Greater<int>> pq;pq.push(4);pq.push(1);pq.push(6);pq.push(9);pq.push(4);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;return 0;
}

这里priority_queue传的是类型，Greater<int> 是一个类型。这就是仿函数的作用。

作用二：

来看代码：

class Date
{
public:Date(int year = 1900, int month = 1, int day = 1): _year(year), _month(month), _day(day){}bool operator<(const Date& d)const{return (_year < d._year) ||(_year == d._year && _month < d._month) ||(_year == d._year && _month == d._month && _day < d._day);}bool operator>(const Date& d)const{return (_year > d._year) ||(_year == d._year && _month > d._month) ||(_year == d._year && _month == d._month && _day > d._day);}friend ostream& operator<<(ostream& _cout, const Date& d);
private:int _year;int _month;int _day;
};ostream& operator<<(ostream& _cout, const Date& d)
{_cout << d._year << "-" << d._month << "-" << d._day;return _cout;
}int main()
{stl::priority_queue<Date*, vector<Date*>> q1;q1.push(new Date(2018, 10, 29));q1.push(new Date(2018, 10, 28));q1.push(new Date(2018, 10, 30));while (!q1.empty()){cout << *q1.top() << " ";q1.pop();}cout << endl;return 0;
}

        这段代码想要对日期进行排序，但是堆里面存的是Data*，不能按照日期进行排序。

这时，可以通过仿函数来改变比较逻辑。

struct PDataLess
{bool operator()(const Date* p1, const Date* p2){return *p1 < *p2;}
};
int main()
{stl::priority_queue<Date*, vector<Date*>, PDataLess> q1;q1.push(new Date(2018, 10, 29));q1.push(new Date(2018, 10, 28));q1.push(new Date(2018, 10, 30));while (!q1.empty()){cout << *q1.top() << " ";q1.pop();}cout << endl;return 0;
}

等等等等