最大堆实现最大优先队列

最大优先队列：队列中最大值（优先级最高的元素）总是在队首。

操作

• front()：返回值最大的元素；
• push(x)：将元素x插入到队列中；
• pop()：删除最大的元素

算法

用最大堆来实现最大优先队列可以获得很好的性能，插入和删除的优先级都是O(logn)，访问最大元素操作的时间复杂度为O(1)。

插入（push）：首先将元素插入到元素的最后，然后将该元素与它的父节点比较，如果它大于它的父节点，则交换两者的位置，重复，直到小于或等于父节点。

删除（pop）：首先将队列的第一个元素与最后一个元素交换位置，然后使队列的长度-1，这样最大元素就被删除了。接下来，就是要让堆保持最大堆的性质，调用maxHeapify(0)即可。maxHeapify是堆操作中的一个最重要的函数，我在堆排序那篇文章中介绍过。

实现

下面是实现的代码，用的是C++的类模板，元素的存储用的是标准容器类vector，这样可以不用关心内存的分配和回收。我发现C++的类模板类的声明和实现必须放在一个头文件中（VC++ 2010），否则链接会出现错误。

#pragma once

#include <vector>
using std::vector;

template<class T>
class MaxPriorityQueue
{
public:
	T front();
	void push(const T& x);
	void pop();
	bool empty();
	int size();

private:
	void maxHeapify(int i);

private:
	vector<T> vct;
};

template<class T> T MaxPriorityQueue<T>::front()
{
	return vct.front();
}

template<class T> void MaxPriorityQueue<T>::push(const T& x)
{
	vct.push_back(x);

	int n = vct.size();
	for (int i = n; i > 1 && vct[i - 1] > vct[i / 2 - 1]; i /= 2)
	{
		std::swap(vct[i - 1], vct[i / 2 - 1]);
	}
}

template<class T> void MaxPriorityQueue<T>::pop()
{
	int n = vct.size();
	std::swap(vct[0], vct[n - 1]);
	vct.pop_back();
	maxHeapify(0);
}

template<class T> bool MaxPriorityQueue<T>::empty()
{
	return vct.empty();
}

template<class T> int MaxPriorityQueue<T>::size()
{
	return vct.size();
}

template<class T> void MaxPriorityQueue<T>::maxHeapify(int i)
{
	int leftChild = i * 2 + 1;
	int rightChild = i * 2 + 2;
	int largest = i;

	if (leftChild < vct.size() && vct[leftChild] > vct[largest])
	{
		largest = leftChild;
	}
	if (rightChild < vct.size() && vct[rightChild] > vct[largest])
	{
		largest = rightChild;
	}

	if (largest != i)
	{
		std::swap(vct[largest], vct[i]);
		maxHeapify(largest);
	}
}