Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

c根据数据结构与算法分析自己实现优先队列

Posted by chan at 2014-03-25 14:46:15 on Problem 3253
Memory: 208K		Time: 16MS
Language: C		Result: Accepted

Source Code
#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 20005
#define MinData 0

struct HeapStruct;
typedef struct HeapStruct PriorityQueue;

struct HeapStruct
{
	int Capacity;
	int CurrentSize;
	int *Array;
};

PriorityQueue* Initialize()
{
	PriorityQueue *H;
	H=(PriorityQueue *)malloc(sizeof(PriorityQueue));
	H->Array=(int *)malloc(sizeof(int)*MAX_SIZE);
	H->Capacity=MAX_SIZE;
	H->CurrentSize=0;
	H->Array[0]=MinData;
	return H;
}

int IsFull(PriorityQueue *H)
{
	if(H->CurrentSize==H->Capacity)
                 return 1;
        else
                 return 0;
}

int IsEmpty(PriorityQueue *H)
{
	if(H->CurrentSize==0)
              return 1;
        else
              return 0;
}

void Insert(PriorityQueue *H,int element)
{
	int i;
	if(IsFull(H))
		return;
	for(i=++H->CurrentSize;H->Array[i/2]>element;i/=2)
		H->Array[i]=H->Array[i/2];
	H->Array[i]=element;
}

int DeletMin(PriorityQueue *H)
{
	int i,Child;
	int MinElement,LastElement;
	if(IsEmpty(H))
		return H->Array[0];
	MinElement=H->Array[1];
	LastElement=H->Array[H->CurrentSize--];
	for(i=1;i*2<=H->CurrentSize;i=Child)
	{
		Child=2*i;
		if(Child!=H->CurrentSize&&H->Array[Child]>H->Array[Child+1])
			Child++;
		if(LastElement>H->Array[Child])
			H->Array[i]=H->Array[Child];
		else
			break;
	}
	H->Array[i]=LastElement;
	return MinElement;
}


int main()
{
	int i,N;
	while(scanf("%d",&N)!=EOF)
	{
		__int64 min1,min2,e,temp;
		__int64 minconst=0;
		PriorityQueue *H=Initialize();
		for(i=0;i<N;i++)
		{
			scanf("%d",&temp);
			Insert(H,temp);
		}
		while(H->CurrentSize>1)
		{
			min1=DeletMin(H);
			min2=DeletMin(H);
			e=min1+min2;
			Insert(H,e);
			minconst+=e;
		}
		printf("%I64d\n",minconst);
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator