首页 > 文章列表 > C++中的堆和优先队列

C++中的堆和优先队列

c++ 优先队列
387 2023-06-11

堆和优先队列是C++中常用的数据结构,它们都具有重要的应用价值。本文将分别对堆和优先队列进行介绍和解析,帮助读者更好地理解和使用它们。

一、堆

堆是一种特殊的树形数据结构,它可以用来实现优先队列。在堆中,每个节点都满足如下性质:

  1. 它的值不小于(或不大于)其父节点的值。
  2. 它的左右子树也是一个堆。

我们将不小于其父节点的堆称为“最小堆”,将不大于其父节点的堆称为“最大堆”。此外,堆通常是一个完全二叉树,即除了最后一层外,其他层的节点都是满的,最后一层的节点从左到右排列。

在C++中,STL库提供了heap和priority_queue两个类来实现堆。其中,heap类提供了堆操作函数,如make_heap、push_heap、pop_heap等,priority_queue类则是基于堆实现的优先队列。下面,我们来看一下heap和priority_queue的用法。

  1. heap类

(1) 创建堆

在创建堆前,需要先创建一个vector类型的数组来存储待排序的数字:

vector<int> v = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3 };

然后,我们可以使用make_heap函数将vector类型的数组转换为堆:

make_heap(v.begin(), v.end(), greater<int>());

其中,greater<int>()表示比较函数,可以控制堆的类型。

(2) 插入元素

在堆中插入元素可以使用push_heap函数,它的用法如下:

v.push_back(7);
push_heap(v.begin(), v.end(), greater<int>());

(3) 删除元素

在堆中删除元素可以使用pop_heap函数,它会将堆顶元素移动到堆的最后一个位置,并从堆中删除该元素。该函数的用法如下:

pop_heap(v.begin(), v.end(), greater<int>());
v.pop_back();

  1. priority_queue类

(1) 创建堆

与heap类不同,priority_queue类可以在声明对象时指定堆的类型,如下所示:

priority_queue<int, vector<int>, greater<int>> q;

这表示创建一个最小堆。

(2) 插入元素

在priority_queue中插入元素可以直接使用push函数,如下所示:

q.push(2);
q.push(4);
q.push(1);
q.push(9);

(3) 删除元素

在priority_queue中删除元素可以直接使用pop函数,如下所示:

q.pop();

二、优先队列

优先队列是一种特殊的队列,它按照优先级为元素进行排序,并在队列前端放置优先级最高的元素,队列尾部放置优先级最低的元素。可以使用堆来实现优先队列。

在C++中,priority_queue类是基于堆实现的优先队列,它可以使用上述heap和priority_queue类中的函数来进行元素插入和删除操作。另外,priority_queue类中还提供了top函数,用于访问优先级最高的元素,如下所示:

priority_queue<int> q;
q.push(2);
q.push(4);
q.push(1);
q.push(9);
cout << q.top() << endl; // 输出1

总结:

本文介绍了C++中的堆和优先队列,并分别解析了堆和优先队列的用法和实现原理。通过学习本文,读者可以更好地理解这两种数据结构,并在实际编程中灵活运用。同时,读者要注意堆和优先队列的使用时机和注意事项,以确保代码的正确性和效率。