배열로 구현한 최대힙과 우선순위 큐를 결합한 형태

후기

1. 역시 간단히 정리하고 코딩시작하는게 훨씬 낫다. //지금은 ㅈ밥이니까 이런거 정리하고 시작하지만 나중엔 이정도 코드는 그냥 바로 코딩 가능하겠지

//최대힙

#include


int A[101] ={-1, 0};
int N = 0;

void insertItem(int key);
void upHeap(int a);
int deleteItem();
void downHeap(int i);

void main()
{
	char sta = 'a';

	/*for(int i =0 ; i<=101; i++)
	{
		printf(" %d",A[i]);
	}*/

	

	int key;
	int heap_max;

	

	while(sta != 'q')
	{
		
		scanf("%c", &sta);

		switch(sta)
		{
		case 'i': 
			scanf("%d", &key);
			insertItem(key);
			printf("0\n"); //입력 완료 표시
			break;
		case 'd' : 
			heap_max = deleteItem();
			printf("%d\n", heap_max);
			break;
		case 'p':
			if(N<1)
				printf("error: No element in heap \n");
			for(int i =1 ; i<=N; i++)
			{
				printf(" %d",A[i]);
			}
			printf("\n");
			break;
		case 'q':
			break;
		}
	}

}

// 

void insertItem(int key)
{
	
	
	if(N>100)
		printf("size error\n");

	A[N+1] = key;
	N++;

	upHeap(N);
}


void upHeap(int a)
{
	if(a==1)
		return;

	int parent = a/2;
	int temp=0;

	if(A[a]<= A[parent])
		return;
	else
	{
		temp = A[a];
		A[a] = A[parent];
		A[parent] = temp;
		upHeap(parent);
	}
}


int deleteItem()
{
	int max = A[1];
	A[1] = A[N];
	A[N] = 0;
	N--;
	
	downHeap(1);

	return max;
}


void downHeap(int i)
{
	int l=2*i; //왼쪽 자식
	int r=2*i+1;  // 오른쪽 자식
	
	int temp;
	
	if(l>N)        // i 의 자식이 둘다 없는 경우
		return;      
	if(r>N)         // i의 자식이 왼쪽 하나인 경우
	{
		if(A[l]<=A[i])
			return;
		else 
		{
			temp=A[l];
			A[l] = A[i];
			A[i] = A[temp];
			return;
		}
	}
	 // 자식이 둘다 있는 경우
	if(A[i]>=A[l] && A[i]>=A[r])  //두 자식이 모두 부모보다 작음 
		return; 
	else                      // 둘중에 하나라도 크면 둘 중 큰 자식과 부모의 위치 바꾸기
	{
		if(A[l]< A[r])           
		{
			temp = A[r];
			A[r] = A[i];
			A[i] = temp;
			downHeap(r);
		}
		else
		{
			temp = A[l];
			A[l] = A[i];
			A[i] = temp;
			downHeap(l);
		}
	}
}