算法与数据结构之优先级队列

前面讲了最大最小堆，现在来讲下最大最小堆的用途——实现优先级队列

复习一下：前面讲的最大最小堆的生成，是把一个数组转换成完全二叉树之后，才转换成最大最小堆的。然后生成的时候先从最下方的叶结点开始生成最大/最小堆。

但是优先级队列的话，往往是原本没有任务在里面，然后再往里面一个个添加任务。这怎么实现呢？

我们分析可以知道，当我们向数组的最后一位添加一个元素的时候，就相当于在一个最大/最小堆上加了一个元素。由于原本的就是最大/最小堆，我们只需要处理好当前插入的元素，使插入后仍然满足最大/最小堆的性质就可以了。

 

那么怎么从优先级队列中取出元素呢？

我们知道，优先级队列中，最高优先级的是堆顶的元素。当我们把堆顶的元素删除之后，要使得剩下的部分仍能够组成一个最大/最小堆，那怎么办呢？

分析之后可以发现，其实就是要找一个元素来替换掉原来堆顶元素的位置。从剩下的元素里寻找，发现，只有移动下标最大的那个元素才能够使得其它部分都不会受到牵连。于是我们就把下标最大的那个元素移动到堆顶。然后，由于剩下的部分都是满足最大最小堆的性质，只需要递归地找到这个堆顶元素应该处在哪个位置，就能使得整个完全二叉树满足最大/最小堆的性质。

 

题目是这样子的：

题目编号为ALDS1_9_C

来自 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_C

Priority Queue
A priority queue is a data structure which maintains a set S of elements, each of with an associated value (key), and supports the following operations:

insert(S,k): insert an element k into the set S
extractMax(S): remove and return the element of S with the largest key
Write a program which performs the insert(S,k) and extractMax(S) operations to a priority queue S. The priority queue manages a set of integers, which are also keys for the priority.

Input
Multiple operations to the priority queue S are given. Each operation is given by "insert k", "extract" or "end" in a line. Here, k represents an integer element to be inserted to the priority queue.

The input ends with "end" operation.

Output
For each "extract" operation, print the element extracted from the priority queue S in a line.

Constraints
The number of operations ≤2,000,000
0≤k≤2,000,000,000

样例输入

insert 8
insert 2
extract
insert 10
extract
insert 11
extract
extract
end

样例输出

8
10
11
2

按照上面的思路，我们就能写出以下的代码

#include<iostream>
using namespace std;

#define MAX 2000000
#define INFTY (1<<30)

int A[MAX + 1], H = 0;


int parent(int i)
{
    return i / 2;
}

int left(int i)
{
    return 2 * i;
}
int right(int i)
{
    return 2 * i + 1;
}


void increaseKey(int i, int key)
{
    if (key < A[i])
        return;
    A[i] = key;
    while (i > 1 && A[parent(i)] < A[i])
    {
        swap(A[parent(i)], A[i]);
        i = parent(i);
    }
}

void ins(int k)
{

    H++;
    A[H] = -INFTY;
    increaseKey(H, k);


}

void maxHeapify(int i)
{
    int L = left(i);
    int R = right(i);
    int P = parent(i);
    int largest;
    if (L <= H && A[L] > A[i]) largest = L;
    else largest = i;
    if (R <= H && A[R] > A[largest])
        largest = R;

    if (largest != i)
    {
        swap(A[i], A[largest]);
        maxHeapify(largest);
    }
}

void ext()
{
    if (H < 1)
        return;
    int maxv = A[1];
    A[1] = A[H];
    A[H] = -INFTY;
    H--;
    maxHeapify(1);
    cout << maxv << endl;


}

int main()
{
    string cmd = "";
    int num;
    cin >> cmd;
    while (cmd != "end")
    {
        if (cmd[0] == 'i')
        {
            cin >> num;
            ins(num);
        }
        else ext();
        cin >> cmd;
    }


}

 

通过标准库来实现队列

众所周知，STL非常的强大，我们可以通过STL来实现优先级队列。

前面介绍过stack（基于LIFO的容器），queue（基于FIFO的容器）。现在这里有个priority_queue，可以实现优先级队列。

如果要实现最大堆那样子的优先级队列的话，在定义的时候只要这样写就可以了：

priority_queue<int>PQ;

但是要实现最小堆的话，就要这样子写了：

priority_queue<int,vector<int>,greater<int>> b;//从小到大

priority_queue的操作和queue相同，push()用于向队列中插入一个元素。pop()用于删除队列首部的一个元素。top()用于访问队列首部的元素。

下面用一段例程演示了priority_queue是如何工作的：

#include<iostream>
#include<queue>
using namespace std;

int main()
{
    priority_queue<int>PQ;
    PQ.push(1);
    PQ.push(8);
    PQ.push(3);
    PQ.push(5);

    cout<<PQ.top()<<endl;
    PQ.pop();
    cout<<PQ.top()<<endl;
    PQ.pop();
    PQ.push(11);
    cout<<PQ.top()<<endl;
    PQ.pop();
    cout<<PQ.top()<<endl;
    PQ.pop();
    cout<<"---------我是分割线-------"<<endl;
    priority_queue<int,vector<int>,greater<int>> b;//从小到大
    b.push(1);
    b.push(8);
    b.push(3);
    b.push(5);

    cout<<b.top()<<endl;
    b.pop();
    cout<<b.top()<<endl;
    b.pop();
    b.push(0);
    cout<<b.top()<<endl;
    b.pop();
    cout<<b.top()<<endl;
    b.pop();

}

用priority_queue来实现上面的题目

当我们使用priority_queue来实现上面的题目的时候，就会发现，代码量少了很多！

#include<iostream>
#include<queue>
#include<string>
using namespace std;

int main()
{
    priority_queue<int> q;

    string cmd="";
    int tmp;
    cin>>cmd;
    while(cmd!="end")
    {
        if(cmd[0]=='i')
        {
            cin>>tmp;
            q.push(tmp);
        }
        else
        {
            cout<<q.top()<<endl;
            q.pop();
        }
        cin>>cmd;
    }
}

欢迎关注我的公众号哦！