2014腾讯实习笔试题第二题是关于优先队列的，不是很熟悉，查阅了一下资料，总结一下：
优先队列是基于堆（二叉堆）实现的，每当加入(push)一个新元素时，会根据优先级，将优先级最大（或最小）的元素按照堆排序（大顶堆，小顶堆）的方式放到堆顶。
如此的话，返回的堆顶元素(top)即优先级最高（或最小）的元素。当然，在pop()操作之后，仍然要进行堆排序，调整元素位置。参考资料如下：
队列的特点是先进先出。通常都把队列比喻成排队买东西，大家都很守秩序，先排队的人就先买东西。但是优先队列有所不同，它不遵循先进先出的规则，而是根据队列中元素的优先权，优先权最大的先被取出。通常把优先队列比喻成现实生活中的打印。一个打印店里有很多打印机，每台机器的性能不一样，有的打印机打印很快，有的打印机打印速度很慢。当这些打印机陆陆续续打印完自己的任务时进入排队等候状态。如果我这个时候要打印一份文件，我选的不是第一个排队的打印机，而是性能最好，打印最快的打印机。
重点:优先级队列，是要看优先级的，谁的优先级更高，谁就先得到权限。不分排队的顺序!
基本操作：
empty() 如果队列为空返回真
pop() 删除对顶元素
push() 加入一个元素
size() 返回优先队列中拥有的元素个数
top() 返回优先队列对顶元素
在默认的优先队列中，优先级高的先出队。在默认的int型中先出队的为较大的数。
下面是最小堆实现的优先队列：
#include <iostream>
#include <vector>
using namespace std;
class Heap
{
public:
Heap(int iSize);
~Heap();
int Enqueue(int iVal);
int Dequeue(int &iVal);
int GetMin(int &iVal);
void printQueue();
protected:
int *m_pData;
int m_iSize;
int m_iAmount;
};
Heap::Heap(int iSize = 100)//注意这里是从0开始，所以如果根是i，那么左孩子是2*i+1，右孩子是2*i+2
{
m_pData = new int[iSize];
m_iSize = iSize;
m_iAmount = 0;
}
Heap::~Heap()
{
delete []m_pData;
}
int Heap::Enqueue(int iVal)//进入堆
{
if (m_iAmount == m_iSize)
{
return 0;
}
m_pData[m_iAmount ++] = iVal;
int iIndex = m_iAmount - 1;
while (m_pData[iIndex] < m_pData[(iIndex - 1) /2])//上浮，直到满足最小堆
{
swap(m_pData[iIndex],m_pData[(iIndex - 1) /2]);
iIndex = (iIndex - 1) /2;
}
return 1;
}
int Heap::Dequeue(int &iVal)//出堆
{
if (m_iAmount == 0)
{
return 0;
}
iVal = m_pData[0];//出堆的数据
m_pData[0] = m_pData[m_iAmount - 1];//最后一个数据放到第一个根上面
-- m_iAmount;//总数减1
int rc = m_pData[0];
int s = 0;
for (int j = 2*s +1; j < m_iAmount; j *= 2)//最后一个数放到第一个位置以后，开始下沉，来维持堆的性质
{
if (j < m_iAmount - 1 && m_pData[j] > m_pData[j+1])
{
++ j;
}
if (rc < m_pData[j])//rc应该插入在s位置上
{
break;
}
m_pData[s] = m_pData[j];
s = j;
}
m_pData[s] = rc;
return 1;
}
int Heap::GetMin(int &iVal)
{
if (m_iAmount == 0)
{
return 0;
}
iVal = m_pData[0];
return 1;
}
void Heap::printQueue()
{
for (int i = 0; i < m_iAmount; ++ i)
{
cout << m_pData[i] << " ";
}
cout << endl;
}
int main()
{
Heap heap;
heap.Enqueue(4);
heap.Enqueue(1);
heap.Enqueue(3);
heap.Enqueue(2);
heap.Enqueue(6);
heap.Enqueue(5);
heap.printQueue();
int iVal;
heap.Dequeue(iVal);
heap.Dequeue(iVal);
heap.printQueue();
return 0;
}
使用方法：
头文件：
声明方式：
1、普通方法：
2、自定义优先级：
首先优先队列是由堆来实现的，所以以后用到优先队列的地方，可以直接用C++中的STL来直接实现，但是最好还是自己实现几次，否则我们只会成为傻瓜，什么东西就知道怎么用，不知道是如何实现的。
优先队列适用的范围很广，比如：
构造哈夫曼编码是找到节点集合中频率最小的两个点，然后合并节点在插入到集合中，再循环。。。
比如操作系统的线程的调度算法，有的是按照优先级来调度的，每次都执行优先级较高的线程
首先把n个有序文件的第一个元素取出来，放到优先队列里面，然后取最小值，然后再插入元素导优先队列，取最小值。。。
比如排序，找中位数，找最大的k个数
（参考来源：http://blog.csdn.net/zhang20072844/article/details/10286997）
2014腾讯实习笔试题——优先队列,布布扣,bubuko.com
原文：http://blog.csdn.net/ziqingfeng/article/details/24001531