【面试题甄选】4 优先级队列，堆积

【面试题精选】4 优先级队列，堆积

优先级队列为，首部元素最大，总是删除当前最大元素。并在尾部插入元素。

删除元素的时间复杂度为O(1)，插入元素的时间复杂度为O(lgn)，效率非常高。

C++实现代码如下：

#include <iostream>
using namespace std;

const int MAX_SIZE = 1024;
int Tail = 0;
int  PriorStack[MAX_SIZE]={0};
bool Push(int num);
void PrintList();
bool inline Exchange(int index1,int index2);
bool inline Clear(int index);
int Pop();

int main(int argc,char * argv[])
{
	Push(6);
	Push(9);
	Push(7);
	PrintList();
	Pop();
	PrintList();
	getchar();
	return 0;
}
void PrintList()
{
	for(int i=1;i<=Tail;i++)
	{
		std::cout<<PriorStack[i]<<"\t";
	}
	std::cout<<std::endl ;
}
/*向优先级队列插入元素，最大的元素在队列首部*/
bool Push(int num)
{
	if(Tail >= MAX_SIZE)
	{
		return false;/*溢出*/
	}
	Tail ++;
	PriorStack[Tail] = num;
	int cur = Tail/2;
	if(cur < 1)
	{
		return true;
	}
	while(true)
	{/*依次于其父节点比较，如果小于则交换元素*/
		if(PriorStack[Tail] > PriorStack[cur])
		{
			Exchange(Tail,cur);
		}
		cur = cur/2;
		if(cur == 0)
		{
			break;
		}
	}
}
/*弹出优先级最高的元素，一般为最大值*/
int Pop()
{
	if(Tail < 1)
	{
		return false;
	}
	int val = PriorStack[1];
	Exchange(1,Tail);/*尾部元素与首部元素交换*/
	Clear(Tail);
	Tail --;
	int p = 1;
	int cur = 2*p;
	while(true)
	{/*如果父节点元素小于子节点元素则予以交换*/
		if(PriorStack[p] < PriorStack[cur])
		{
			Exchange(p,cur);
		}
		p = cur;
		cur = p *2;
		if(p >= Tail)
		{
			break;
		}
	}
	return val;
}
/*交换两个位置上的元素*/
bool inline Exchange(int index1,int index2)
{
	int tmp = PriorStack[index2];
	PriorStack[index2] = PriorStack[index1];
	PriorStack[index1] =tmp;
	return true;
}
/*清空某个位置的元素*/
bool inline Clear(int index)
{
	PriorStack[index] = 0;
	return true;
}