11 - 해시 4 Hashing - Hard Version

//           ，   26 ，         
//         ，                  
#include 
#include 

#define Max 1000
#define MinData -100000001
int Graph[Max][Max];

typedef struct HeapStruct *MinHeap;
struct HeapStruct{
	int *elements;
	int size;
	int capacity;
};

void TopSort(int hash[], int indegree[], int N, int ans[]);
MinHeap Creats(int MaxSize);
void Min_Insert(MinHeap H, int item);
int Min_Delete(MinHeap H);

int main(int argc, char const *argv[])
{
	// freopen("test.txt", "r", stdin);
	int N, cnt;
	scanf("%d", &N);
	int indegree[N], hash[N]; 
	for (int i = 0; i < N; i++){
		scanf("%d", &hash[i]);
		if (hash[i] >= 0){
			indegree[i] = (i - hash[i] % N + N) % N;
			cnt++;	//         
		}
		else
			indegree[i] = -1;
		for (int j = 0; j < N; j++)
			Graph[i][j] = 0;
	}
	for (int i = 0; i < N; i++){
		if (hash[i] < 0)
			continue;
		int j = hash[i] % N;
		for (int t = 0; t < indegree[i]; t++){
			Graph[j][i] = 1;
			j = (j+1) % N;	
		}
	}
	int ans[N];
	TopSort(hash, indegree, N, ans);
	for (int i = 0; i < cnt; i++){
		if (i != 0)
			printf(" ");
		printf("%d", ans[i]);
	}
	return 0;
}

void TopSort(int hash[], int indegree[], int N, int ans[])
{
	MinHeap H = Creats(N);
	for (int i = 0; i < N; i++){
		if (indegree[i] == 0)
			Min_Insert(H, hash[i]);
	}
	int cnt = 0;
	while (H->size){
		int v = Min_Delete(H);
		ans[cnt++] = v;
		v = v % N; 
		for (int i = 0; i < N; i++){
			if (Graph[v][i] == 1){
				if (--indegree[i] == 0)
					Min_Insert(H, hash[i]);
			}
		}	
	}
}

MinHeap Creats(int MaxSize)
{
	MinHeap H = (MinHeap)malloc(sizeof(struct HeapStruct));
	H->elements = (int*)malloc(sizeof(int)*(MaxSize + 1));//  elemens[0]    ， [1]    ，    MaxSize+1  
	H->size = 0;
	H->capacity = MaxSize;
	H->elements[0] = MinData;// elements[0]    
	return H;
}

void Min_Insert(MinHeap H, int item)
{
	int i;
	i = ++H->size;//i                 
	for(; H->elements[i/2] > item; i/=2) //               
		H->elements[i] = H->elements[i/2];
	H->elements[i] = item;
}

int Min_Delete(MinHeap H)
{
	int Parent, Child;
	int MinItem, tmp;
	MinItem = H->elements[1];
	tmp = H->elements[H->size--];
	for (Parent = 1; Parent*2 < H->size; Parent = Child){
		Child = Parent * 2;
		if (Child != H->size && (H->elements[Child] > H->elements[Child+1]))
			Child++;
		if (tmp <= H->elements[Child])
			break;
		else
			H->elements[Parent] = H->elements[Child];
	}
	H->elements[Parent] = tmp;
	return MinItem;
}