用堆实现的优先队列

通过完全二叉树而得到的最大（小）堆 ， 从而得到快速的优先队列。

最大（小）堆：是一颗完全二叉树 ，   只不过所有根节点都大于（小于）其子节点。

• 当往堆中增加一个元素时，需要重新排列这个最大堆 ， 但时间只需要log2(n+1)

• 当删除根元素时 ， 也需要重新排列 ， 但时间也是log2(n+1)

插入元素：

        因为堆是一个完全二叉树 ， 所以新加入的元素都是加入在最后面的那个位置 ， 如图：

加如元素13——    

加入的新元素首先要和它的父亲比较 ， 如果比其父亲节点大，则和其父亲节点交换，否则就完成加入。

void max_heap::push(int x)   //向最大堆中压入元素
{
	int k ;
	
	k = ++length;

	while(k > 1)
	{
		if(x > heap[k/2])
		{
			heap[k] = heap[k/2];
			k = k/2;
		}
		else break;
	}
	heap[k] = x;
}

删除元素：

       删除元素就是把根节点删除 ， 当把根节点删除之后 ，  就把最后那个节点提到根节点的位置 ， 如图：

删除根元素后

实现：将最后的元素提到跟节点的位置之后 ， 就需要用这个跟节点和其儿子比较 ， 然后再重复插入元素一样的步骤   。        

代码：

void max_heap::pop()
{
	int x = 1, y;
	int z = heap[length--];
	
	y = 2;
	while(y <= length)//判断其儿子是否存在 ， 
	{
//编码的方法
		if(y < length && heap[y] < heap[y+1])  y += 1;
		
		if(z >= heap[y])  break;
		else
		{
			heap[x] = heap[y];
			x = y;
			y *= 2;
		}
	}
	heap[y] = z;

}

#include <iostream>
using namespace std;

class max_heap
{
public:
	max_heap()  {length = 0; }
	max_heap(int x) {length = 0; }
//	~max_heap() {delete []heap; }
	void push(int x);
	int front();
	void pop();
	int empty();

private:
	int max_size ;
	int length;
	int heap[100];

};

void max_heap::push(int x)   //向最大堆中压入元素
{
	int k ;
	
	k = ++length;

	while(k > 1)
	{
		if(x > heap[k/2])
		{
			heap[k] = heap[k/2];
			k = k/2;
		}
		else break;
	}
	heap[k] = x;
}

int max_heap::front()
{
	return heap[1];
}

int max_heap::empty()
{
	if(length != 0)  return 0;
	else return 1;
}

void max_heap::pop()
{
	int x = 1, y;
	int z = heap[length--];
	
	y = 2;
	while(y <= length)//判断其儿子是否存在 ， 
	{
//编码的方法
		if(y < length && heap[y] < heap[y+1])  y += 1;
		
		if(z >= heap[y])  break;
		else
		{
			heap[x] = heap[y];
			x = y;
			y *= 2;
		}
	}
	heap[y] = z;

}

int main()
{
	max_heap s;
	s.push(3);
	cout<<s.front()<<endl;
	return 0;
}

用堆实现的优先队列,布布扣,bubuko.com

用堆实现的优先队列

原文：http://blog.csdn.net/zengchen__acmer/article/details/20857331