优先队列实现

定义

优先队列是一种抽线数据类型，优先队列中的每个元素都有优先级，优先级高的先出队，而优先级相同的则按照入队的顺序出队。优先队列往往通过二叉堆来实现。
二叉堆的性质

• 根节点元素值始终大于/小于左右节点的值
• 完全二叉树

使用二叉堆实现优先队列

二叉堆通常使用数组来表示，下图展示了如何使用数组来表示二叉堆

构建最大堆类

根据根节点元素的值小于或者大于左右节点的值，可以分为最小堆（小顶堆）或者最大堆（大顶堆），主要区别在于堆顶是最小值还是最大值。
优先队列存在从堆尾插入元素和删除堆顶元素两种操作方法，因此具体的类实现如下：

class MaxPQ
{
    // 成员变量
    vector pq;	 // 用于存储大顶堆的元素
    int N = 0;				// 当前堆包含的元素个数
    
    public:
    MaxPQ(int cap)  
    {
        // 开辟空间
        pq.resize(cap + 1);		// 序号为0不存储元素
    }
    
    // 返回当前队列中最大元素
    int max()
    {
        return pq[1];
    }
    // 插入元素e，即将元素e添加到队尾，然后上浮到合适的位置
    void insert(int e);
    
    // 删除并返回当前队列中最大元素
    int delMax();
    
    // 上浮第k个元素，以维护最大堆的性质
    void swim(int k);
    
    // 下沉第k个元素，以维护最大堆性质
    void sink(int k);
    
    // 交换数组的两个元素
    void exch(int i, int j)
    {
        int temp = pq[j];
        pq[j] = pq[i];
        pq[i] = temp;
    }
    // 判断pq[i] 是否比pq[j]小
    bool less(int i, int j)
    {
        return pq[i] < pq[j] ? true : false;
    }
    // 返回当前节点父节点索引
    int parent(int root)
    {
        return root / 2;
    }
    // 返回左子节点的索引
    int left(int root)
    {
        return 2 * root;
    }
    int right(int root)
    {
        return 2 * root + 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

实现swim和sink函数

从子节点的角度来看，如果某个节点A比他的父节点B大，那么A不应该在子节点，而应该把A节点上浮把父节点B换下来，自己做父节点。

void MaxPQ::swim(int k)
{
    // 给的节点与父节点相比
    while(k > 1 && less(parent(k), k))
    {
        // 交换节点
        exch(parent(k), k);
        k = parent(k);
    }
}
1
2
3
4
5
6
7
8
9
10

从父节点的角度来看，如果父节点A与其两个子节点比较大小，如果A不是最大的就需要调整位置，进行下沉把较大的子节点和A交换。

void MaxPQ::sink(int k)
{
    // 如果沉到堆底，就不下沉了
    while(left(k) <= N)
    {
        // 先假设左边节点较大,返回左边节点的索引
        int maxer = left(k);
        // 如果右边节点存在，比一下大小
        if(right(k) <= N && less(maxer, right(k))
        {
            maxer = right(k);
        }
        // 如果节点k比两个孩子都大，就不必下称了
        if(less(maxer, k)) break;
        exch(k, maxer);
        k = maxer;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

队尾插入元素

思路：从队尾插入节点N，然后将节点N上浮到合适的位置。

void MaxPQ::insert(int e)
{
    N++;
    // 把先添加的元素查到最后
    pq[N] = e;
    // 让它上浮到正确的位置
    swim(N);
}
1
2
3
4
5
6
7
8

删除队顶最大元素

思路：先将堆顶元素A和堆底元素B进行交换，然后删除元素A，最后让元素B下沉到合适的位置

int MaxPQ::delMax()
{
    int max = pq[1];
    // 交换
    exch(1, N);
    pq[N] = NULL;
    N--;
    // 让B下沉
    sink(1);
    return max;
}
1
2
3
4
5
6
7
8
9
10
11

测试

#include 
#include 
using namespace std;
class MaxPQ
{
    private:
        // 存储元素的数组
        vector pq;
        // 当前PQ中的元素个数
        int N ;
    public:
        // 构造函数
        MaxPQ(int capacity)
        {
            // 索引0不用，所以需要多分配一个空间
            pq.resize(capacity + 1);
            N = 0;
        }
        // 返回当前队列中最大元素
        int max()
        {
            return pq[1];
        }
        
        // 插入元素
        void insert(int e)
        {
            // 将要插入的元素添加到堆底的位置，然后上浮到正确位置
            ++N;
            // 先将新的元素添加到最后
            pq[N] = e;
            // 然后上浮到正确位置
            swim(N);
            
        }
        // 删除并返回当前数组中最大元素
        int delMax()
        {
            // 先将堆顶的元素A和堆底元素B位置对调，然后删除A，将B下沉到合适位置
            int max = pq[1];
            // 兑换
            exch(1, N);
            // 删除
            --N;
            // 下称
            sink(1);
            return max;
        }
        /* ******************* helper functions ********************* */
        int parent(int root)
        {
            return root / 2;
        }
        int left(int root)
        {
            return root * 2;
        }
        int right(int root)
        {
            return root * 2 + 1;
        }
        // 上浮第k个元素，以维护最大堆性质
        void swim(int k)        // 定位为子节点
        {
            // 如果某个节点A比它的父节点大，那么对A上浮
            while(k > 1 && less(parent(k), k))  // k> 1才有父节点
            {
                cout << "swin: " << pq[k] << endl;
                // 交换序号为parent(k) 和 k 的值
                exch(parent(k), k);
                // 交换完后k位于父节点处
                k = parent(k);
            }
        }
        // 下沉第k个元素
        void sink(int k)        // 定位为父节点
        {
            // 如果某个节点A比它的子节点小，则对A下沉
            // 需要判断A与其两个子节点比较大小，判断A是否为最大值
            while(left(k) <= N)
            {
                // 先假设左节点为最大值
                int older = left(k);
                // 如果右节点存在，比较大小
                while(right(k) <= N && less(left(k), right(k)))
                {
                    // 最大值为右节点
                    older = right(k);
                }
                // 父节点与最大子节点进行比较
                if(less(older, k)) break;
                
                // 否则交换并下沉k节点
                cout << "sink: " << pq[k] << endl;
                exch(older, k);
                k = older;
            }
        }
        
        // 交换数组的两个元素
        void exch(int i, int j)
        {
            // cout << "i: " << i << " j: " << j << endl;
            int temp = pq[i];
            pq[i] = pq[j];
            pq[j] = temp;
            
        }
        
        // 比较pq[i]是否小于pq[j]
        bool less(int i, int j)
        {
            return pq[i] < pq[j];
        }
};

int main()
{
    MaxPQ data(10);
    
    data.insert(2);
    data.insert(5);
    data.insert(6);
    data.insert(10);
    data.delMax();
    cout << data.max() << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

C++中优先队列的使用

priority_queue在C++的queue库中实现，优先队列的底层实现是heap堆，可以在任意时刻从堆底插入元素，但是只可以访问堆顶元素。提供了如下一些成员函数：

• empty()：判断是否为空
• size()：返回优先队列中元素的个数
• top()：堆顶 access top element
• push(): insert element
• pop(): remove top element
• swap(): 交换内容

---

类定义

template ,
  class Compare = less > class priority_queue;
1
2

与stack和queue类似，priority_queue也是container adaptor，设计用来保证队顶元素为最大值。

• Type：所有元素的数据类型
• Container： vector和dequeue可以作为底层的容器，默认情况下，使用vector
• compare：排序函数，可以是一个函数pointer或者函数object

//最小堆
priority_queue ,greater > q;
//最大堆
priority_queue ,less >q;

//greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）
1
2
3
4
5
6

1. 使用基础类型

#include 
#include 
#include 
using namespace std;

int main() 
{
    priority_queue a; // 默认为最大堆
    a.push(3);
    a.push(1);
    a.push(6);
    while (!a.empty()) 
    {
        cout << a.top() << '\n';
        a.pop();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2. 使用pair

对于用户自定义的数据结构，常见有两种比较规则来初始化priority_queue对象，一个是重载小于运算符，另一个是使用重载函数操作符的类对象。在2. 使用pair中介绍了重载（）的方法，在3.使用自定义类型中介绍了小于运算符重载的方法

#include 
#include 
#include 
using namespace std;
// 重载()符号
typedef struct
{
    bool operator() (const pair& a, const pair& b)
    {
        // 最大堆
        return a.second < b.second;
        // 最小堆
        // return a.second > b.second;
    }
}cmp;
int main() 
{
    priority_queue< pair, vector>, cmp > a;
    pair b(1, 2);
    pair c(1, 3);
    pair d(2, 5);
    a.push(d);
    a.push(c);
    a.push(b);
    while (!a.empty()) 
    {
        cout << a.top().first << ' ' << a.top().second << '\n';
        a.pop();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

3. 使用自定义类型

#include 
#include 
using namespace std;


typedef struct Exp1
{
    // 运算符重载
    int data;
    Exp1(int a) { data = a;}
    bool operator<(const Exp1& a)   const
    {
        return data < a.data;   // <待参考值，比较值>
    }
} EXP1;
int main()
{
    Exp1 a(1);
    Exp1 b(2);
    Exp1 c(4);
    priority_queue d;
    d.push(a);
    d.push(c);
    d.push(b);
    
    while(!d.empty())
    {
        cout << "top: " << d.top().data << " ";
        d.pop();
    }
    cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

参考链接

• https://cloud.tencent.com/developer/article/1695851
• https://blog.csdn.net/liu2012huan/article/details/52932494
• https://cplusplus.com/reference/queue/priority_queue/priority_queue/