C++：堆排序算法的简单讲解，仿函数的介绍和应用，优先级队列priority_queue的常用接口和模拟实现
·
目录
1.堆排序算法
1.1 堆排序的介绍
“堆排序”就是一个说法，实际上就是将一个数组模拟构造成完全二叉树的结构，通过对每个元素进行“向上调整算法”或“向下调整算法”使得数组中的数据变得有序。
“大（根）堆”不是指的是开头元素最大、从大到小排列的有序数组，而是指这个数组每个节点的值都大于或等于它的左右孩子节点的值；
“小（根）堆”不是指的是开头元素最小、从小到大排列的有序数组，而是指这个数组每个节点的值都小于或等于它的左右孩子节点的值。
1.2 向上调整、向下调整算法
向上调整算法和向下调整算法的精髓在于“寻找父亲的左孩子和右孩子”，即每个节点的左节点和右节点，然后将“孩子”和“父亲”进行比较，不断交换进行调整，最终使数组变得有序。
堆排序的时间复杂度为O(n*logn)。
void AdjustUp(int child) // 默认排小堆（这个数组每个节点的值都小于或等于它的左右孩子节点的值） { int parent = (child - 1) / 2; //找孩子节点的父亲节点 while (child > 0) //当parent=0的时候是最后一轮循环，随后child=parent=0则退出循环，所以退出循环的条件是 child > 0 { if (v[child] < v[parent]) { swap(v[child], v[parent]); //如果孩子比父亲的数据小，则将二者交换 } //更新child和parent child = parent; parent = (child - 1) / 2; } }void AdjustDown(int n, int parent) // 默认排小堆（这个数组每个节点的值都小于或等于它的左右孩子节点的值） { int child = parent * 2 + 1; //找父亲节点的左孩子，默认左孩子较小 while (child < n) //当parent=0的时候是最后一轮循环，随后child=parent=0则退出循环，所以退出循环的条件是 child > 0 { //找到左孩子和右孩子中较大的那个 if (child + 1 < n && v[child] > v[child + 1]) { child++; } if (v[child] < v[parent]) { swap(v[child], v[parent]); //如果孩子比父亲的数据小，则将二者交换 } //更新child和parent parent = child; child = parent * 2 + 1; } }
1.3 堆排序
当我们有了向上调整算法和向下调整算法之后，我们就可以尝试用这个算法进行排序。
注意：向上调整算法AdjustUp和向下调整算法AdjustDown只是能保证第一个元素是最大值或最小值，但是其他元素的大小顺序是没有完全排列好的，而排序是要将所有的数据排列有序，这时我们要将这二者结合在一起使用。
void HeapSort() { /* 这个函数中，AdjustUp和AdjustDown都是建小堆的算法，目的是“找最小值”， 从而依次将最小值放在后面，因此实现从大到小排序 也就是说，AdjustUp和AdjustDown只是能保证第一个元素是最大值或最小值，但是 其他元素的大小顺序是没有完全排列好的 并且得到规律：建小堆的AdjustUp和AdjustDown可以实现从大到小排序（降序，建小堆） 建大堆的AdjustUp和AdjustDown可以实现从小到大排序（升序，建大堆） */ for (size_t i = 0; i < v.size() ; i++) { AdjustUp(i); } /* 建立小堆之后第一个元素一定是最小值，将这个值与最后一个值进行交换， 就将最后一个值的顺序确定下来了，接着对剩余元素从零开始进行向上调整， 此时第一个元素为确定出新的最小值元素，继续将其放在倒数第二个位置上…… 不断重复这个过程，就将全部元素的顺序从大到小排列好了 */ int end = v.size() - 1; for (int i = end; i >= 0; i--) { swap(v[0], v[i]); AdjustDown(i, 0); } }
1.4 完整代码
#pragma once
namespace my
{
class sort
{
public:
sort()
{}
void AdjustUp(int child) // 默认排小堆（这个数组每个节点的值都小于或等于它的左右孩子节点的值）
{
int parent = (child - 1) / 2; //找孩子节点的父亲节点
while (child > 0) //当parent=0的时候是最后一轮循环，随后child=parent=0则退出循环，所以退出循环的条件是 child > 0
{
if (v[child] < v[parent])
{
swap(v[child], v[parent]); //如果孩子比父亲的数据小，则将二者交换
}
//更新child和parent
child = parent;
parent = (child - 1) / 2;
}
}
void AdjustDown(int n, int parent) // 默认排小堆（这个数组每个节点的值都小于或等于它的左右孩子节点的值）
{
int child = parent * 2 + 1; //找父亲节点的左孩子，默认左孩子较小
while (child < n) //当parent=0的时候是最后一轮循环，随后child=parent=0则退出循环，所以退出循环的条件是 child > 0
{
//找到左孩子和右孩子中较大的那个
if (child + 1 < n && v[child] > v[child + 1])
{
child++;
}
if (v[child] < v[parent])
{
swap(v[child], v[parent]); //如果孩子比父亲的数据小，则将二者交换
}
//更新child和parent
parent = child;
child = parent * 2 + 1;
}
}
void HeapSort()
{
/*
这个函数中，AdjustUp和AdjustDown都是建小堆的算法，目的是“找最小值”，
从而依次将最小值放在后面，因此实现从大到小排序
也就是说，AdjustUp和AdjustDown只是能保证第一个元素是最大值或最小值，但是
其他元素的大小顺序是没有完全排列好的
并且得到规律：建小堆的AdjustUp和AdjustDown可以实现从大到小排序（降序，建小堆）
建大堆的AdjustUp和AdjustDown可以实现从小到大排序（升序，建大堆）
*/
for (size_t i = 0; i < v.size() ; i++)
{
AdjustUp(i);
}
/*
建立小堆之后第一个元素一定是最小值，将这个值与最后一个值进行交换，
就将最后一个值的顺序确定下来了，接着对剩余元素从零开始进行向上调整，
此时第一个元素为确定出新的最小值元素，继续将其放在倒数第二个位置上……
不断重复这个过程，就将全部元素的顺序从大到小排列好了
*/
int end = v.size() - 1;
for (int i = end; i >= 0; i--)
{
swap(v[0], v[i]);
AdjustDown(i, 0);
}
}
void print()
{
for (auto a : v)
{
cout << a << " ";
}
cout << endl;
}
private:
vector<int> v={8,4,1,2,3};
};
}
2.仿函数
1.1 仿函数的介绍
定义：
仿函数(functor)，就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了。
C++STL其中包含4个组件，分别为算法、容器、函数、迭代器。而仿函数就是分在函数中用于模板类和模板函数中。
特点：
1.仿函数不是函数是类
2.仿函数重载了()运算符，拥有函数的行为
1.2 实例：比较大小与冒泡函数
下面这个是普通的冒泡函数及其调用
void BubbleSort(int* a, int size) { for (int i = 0; i < size; i++) { for (int j = 0; j < size - i - 1; j++) { if (a[j] < a[j + 1]) { swap(a[j + 1], a[j]); } } } } int main() { int a[] = { 5,8,4,9,3,5,7 }; BubbleSort(a, sizeof(a) / sizeof(int)); return 0; }将其修改一下，变成使用仿函数实现比较大小的操作
template <class T> class Less { public: bool operator()(const T& a1, const T& a2) { return a1 < a2; } }; template <class T> class Greater { public: bool operator()(const T& a1, const T& a2) { return a1 > a2; } }; template <class Compare> void BubbleSort(int* a, int size, Compare com) { for (int i = 0; i < size; i++) { int flag = 0; for (int j = 0; j < size - i - 1; j++) { //if (a[j] < a[j + 1]) if(com(a[j], a[j + 1])) { swap(a[j + 1], a[j]); flag = 1; } } /* 这里的flag表示一趟冒泡排序是否有调整，若没有调整，则说明排序已经完成，直接跳出函数 用该方法可以提高冒泡排序的效率 */ if (flag == 0) { break; } } } int main() { int a[] = { 5,8,4,9,3,5,7 }; BubbleSort(a, sizeof(a) / sizeof(int), Less<int>()); //表示前一个元素比后一个元素小则进行交换，结果为降序 for (auto e : a) { cout << e << " "; } cout << endl; BubbleSort(a, sizeof(a) / sizeof(int), Greater<int>()); //表示前一个元素比后一个元素大则进行交换，结果为升序 for (auto e : a) { cout << e << " "; } cout << endl; return 0; }注意：这里面的函数调用时第三个参数为 Less<int>() 或 Greater<int>()，传的是具体的类型实例化的对象，使用的是匿名对象。
后面会出现直接传类名的情况，注意区分！
3.优先级队列priority_queue
3.1 priority_queue的介绍
优先队列优先级队列是一种容器适配器，根据一些严格的弱排序标准，专门设计为它的第一个元素始终是它所包含的元素中最大的一个。
这种结构类似于堆，可以随时插入元素，并且只能检索最大堆元素（优先级队列中顶部的元素）。
优先级队列作为容器适配器实现，容器适配器是使用特定容器类的封装对象作为其底层容器的类，提供一组特定的成员函数来访问其元素。元素从特定容器的“背面”弹出，这称为优先级队列的顶部。（默认的优先级为最大的元素，默认数据为降序排列）
底层容器可以是任何标准容器类模板或其他一些专门设计的容器类。容器应通过随机访问迭代器进行访问。
3.2 priority_queue的常用接口
3.2 priority_queue的模拟实现
namespace my { template <class T> class Less { public: bool operator()(const T& a1, const T& a2) { return a1 < a2; } }; template <class T> class Greater { public: bool operator()(const T& a1, const T& a2) { return a1 > a2; } }; //默认用less，less在头文件 <functional> 中， //默认是降序，建大堆，取的是最大值 template <class T, class Container = vector<T>, class Compare = Less<T> > class priority_queue { public: void AdjustUp(int child) // // 默认排大堆（这个数组每个节点的值都大于或等于它的左右孩子节点的值） { Compare com; int parent = (child - 1) / 2; //找孩子节点的父亲节点 while (child > 0) //当parent=0的时候是最后一轮循环，随后child=parent=0则退出循环，所以退出循环的条件是 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 child = parent; parent = (child - 1) / 2; } else { break; } } } void AdjustDown(int parent) // 默认排大堆（这个数组每个节点的值都大于或等于它的左右孩子节点的值） { Compare com; int child = parent * 2 + 1; //找父亲节点的左孩子，默认左孩子较大 while (child < _con.size()) //当parent=0的时候是最后一轮循环，随后child=parent=0则退出循环，所以退出循环的条件是 child > 0 { //找到左孩子和右孩子中较大的那个 //if (child + 1 < _con.size() && _con[child] < _con[child + 1]) if (child + 1 < _con.size() && com(_con[child], _con[child + 1])) { child++; } //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; child = parent * 2 + 1; } else { break; } } } void push(const T& val) { _con.push_back(val); AdjustUp(_con.size() - 1); } void pop() { swap(_con.front(), _con.back()); _con.pop_back(); AdjustDown(0); } const T& top() { return _con.front(); } size_t size() const { return _con.size(); } bool empty() const { return _con.empty(); } private: Container _con; }; }注意：
1.向上调整算法AdjustUp和向下调整算法AdjustDown需要稍微修改一下，并加入仿函数使其既能建大堆，还能建小堆。
2.在push中，将数据尾插后一定要从尾部向上调整，确保数据有序。
3.在pop中，应先将收尾数据互换，然后将数据尾删，之后一定要从头开始向下调整，确保数据有序。
4.在实例化对象的时候应该是“my::priority_queue<int, vector<int>,my::Greater<int> > q”，传第二个和第三个模版参数时只需传类型，注意类型中的模版参数不要丢掉。
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
28
0- 0
已为社区贡献2条内容
所有评论(0)