heap.h

时间复杂度为O(ElogV)的Dijkrastra算法的实现

struct Vertex
{
	int row, col;
	unsigned int d;
};
struct PreVert
{
	int prerow, precol;
};

class Heap
{
private:
	vector<Vertex> A;
	int size;
	int column;

	int Parent(int i) {return i/2;}
	int Left(int i) {return 2*i;}
	int Right(int i) {return 2*i+1;}

public:
	vector<int> M;
	vector<PreVert> Path;

	Heap(int m, int n) 
	{
		A.resize(m*n+1);
		M.resize(m*n);
		Path.resize(m*n);
		column = n;
		size = m*n;
	}
	~Heap()
	{
		size = 0;
	}
	void Add(int i, Vertex& x)
	{
		A[i] = x;
		M[x.row * column + x.col] = i;
	}
	int HeapSize(){return size;}
	Vertex GetVertex(int row, int col)
	{
		int i = M[row * column + col];
		return A[i];
	}
	void output()
	{
		for(int i=1; i<=size; i++)
			printf("(%d %d %d)-", A[i].row, A[i].col, A[i].d);
		printf("\n");
		for(i=1; i<=size; i++)
		{
			int k = M[A[i].row*column + A[i].col];
			printf("(%d %d %d)-", A[k].row, A[k].col, A[k].d);
		}
		printf("\n");
	}

	void Heapify(int i)
	{
		int l = Left(i);
		int r = Right(i);
		int least;
		if(l<=HeapSize() && A[l].d < A[i].d)
			least = l;
		else
			least = i;
		if(r<=HeapSize() && A[r].d < A[least].d)
			least = r;
		if(least != i)
		{
			Vertex temp = A[i];
			A[i] = A[least];
			A[least] = temp;
			M[A[i].row * column + A[i].col] = i;
			M[A[least].row * column + A[least].col] = least;
			Heapify(least);
		}
	}
	
	Vertex ExtractMin()
	{
		Vertex min = A[1];
		A[1] = A[size];
		size = size - 1;
		Heapify(1);
		return min;
	}

	void DecreaseKey(Vertex& u, int vrow, int vcol, unsigned int wuv)
	{
		int vnum = vrow * column + vcol;
		int i = M[vnum];
		if(i<0)
			return;
		unsigned int newd = u.d + wuv;
		if(newd < A[i].d)
		{
			Path[vnum].prerow = u.row;
			Path[vnum].precol = u.col;

			A[i].d = newd;
			int p = Parent(i);
			while(i>1 && A[p].d > A[i].d)
			{
				Vertex temp = A[i];
				A[i] = A[p];
				A[p] = temp;
				M[A[i].row * column + A[i].col] = i;
				M[A[p].row * column + A[p].col] = p;
				i = p;
				p = Parent(i);
			}
		}
	}
};