用堆实现的优先队列 - JAVA

最近从新学习了一编数据结构，发现自己以前根本就没认真去学习这门课程。

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

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

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

插入元素：

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

加如元素13――

< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+vNPI67XE0MLUqsvYytfPyNKqus3L/LXEuLjH17HIvc8go6wgyOe5+7HIxuS4uMfXvdq147Tzo6zU8rrNxuS4uMfXvdq14727u7ujrLfx1PK+zc3qs8m808jroaM8L3A+CjxwPjxicj4KPC9wPgo8cD48cHJlIGNsYXNzPQ=="brush:java;">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 
  
   
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<