C 언어 는 최대 쌓 기 최소 쌓 기 및 쌓 기 정렬 을 실현 합 니 다.

3658 단어 알고리즘
더 미 는 배열 로 표시 할 수 있 으 며, 그 중에서 a [0] 는 최소 치, 보초병 표 를 넣 을 수 있다.
 삽입 작업 은 배열 의 마지막 에 두 고 이 점 의 부모 노드 가 이 삽입 값 보다 크 면
그러면 하위 노드 의 값 을 부모 노드 로 대체 하고 부모 노드 를 계속 위로 비교 하 며 적당 한 위치 로 이동 하여 해당 하 는 값 을 부여 합 니 다.
pop 작업, pop 의 값 은 a [1] 입 니 다. 첫 번 째 노드 부터 뒤의 값 PercDown (H, 1) 을 조정 합 니 다.
어 지 러 운 배열 을 정 하 는데, 어떻게 직접 그 를 한 무더기 로 만 들 수 있 습 니까?
/ * 마지막 노드 의 부모 노드 부터 뿌리 노드 까지 1 * /    for (i = H->Size / 2; i>0; i--)         PercDown(H, i);
#include
#include
#define N  10005
typedef int ElementType;
typedef struct HNode *Heap; /*        */
struct HNode {
	ElementType *Data; /*         */
	int Size;          /*          */
	int Capacity;      /*        */
};
typedef Heap MaxHeap; /*     */
typedef Heap MinHeap; /*     */

#define MAXDATA 1000  /*                          */
#define MINDATA -1000



MinHeap CreateMinHeap(int MaxSize)
{ /*      MaxSize       */

	MaxHeap H = (MaxHeap)malloc(sizeof(struct HNode));
	H->Data = (ElementType *)malloc((MaxSize + 1) * sizeof(ElementType));
	H->Size = 0;
	H->Capacity = MaxSize;
	H->Data[0] = MINDATA; /*   "  "             */

	return H;
}


bool IsFull(MinHeap H)
{
	return (H->Size == H->Capacity);
}



bool Insert(MinHeap H, ElementType X)
{ /*    X     H,  H->Data[0]        */
	int i;
	if (IsFull(H)) {
		printf("     ");
		return false;
	}
	i = ++H->Size; /* i                  */
	for (; H->Data[i / 2] > X; i /= 2)
		H->Data[i] = H->Data[i / 2]; /*   X */
	H->Data[i] = X; /*  X   */
	return true;
}

#define ERROR -1 /*                           */



bool IsEmpty(MinHeap H)
{
	return (H->Size == 0);
}



ElementType Deletemin(MinHeap H)
{
	/*     H           ,        */
	int Parent, Child;
	ElementType MinItem, X;

	if (IsEmpty(H)) {
		printf("      ");
		return ERROR;
	}

	MinItem = H->Data[1]; /*             */
						  /*                           */
	X = H->Data[H->Size--]; /*             */
	for (Parent = 1; Parent * 2 <= H->Size; Parent = Child) {
		Child = Parent * 2;
		if ((Child != H->Size) && (H->Data[Child]>H->Data[Child + 1]))
			Child++;  /* Child            */
		if (X <= H->Data[Child]) break; /*         */
		else  /*   X */
			H->Data[Parent] = H->Data[Child];
	}
	H->Data[Parent] = X;

	return MinItem;
}


/*-----------       -----------*/
void PercDown(MinHeap H, int p)
{ /*   : H  H->Data[p]            */
	int Parent, Child;
	ElementType X;
	X = H->Data[p]; /*           */
	for (Parent = p; Parent * 2 <= H->Size; Parent = Child) {
		Child = Parent * 2;
		if ((Child != H->Size) && (H->Data[Child]>H->Data[Child + 1]))
			Child++;  /* Child            */
		if (X <= H->Data[Child]) break; /*         */
		else  /*   X */
			H->Data[Parent] = H->Data[Child];
	}
	H->Data[Parent] = X;
}

void BuildHeap(MinHeap H)
{ /*   H->Data[]    ,            */
  /*       H->Size       H->Data[]  */
	int i;
	/*              ,    1 */
	for (i = H->Size / 2; i>0; i--)
		PercDown(H, i);
}

int main()
{
	int a[N], b[N];
	int n;
	scanf_s("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf_s("%d", &a[i]);
	}
	for (int i = 0; i < n; i++)
	{
		scanf_s("%d", &b[i]);
	}
	MinHeap H = CreateMinHeap(N);
	int k = 1;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			H->Data[k] = a[i] + b[j];
			k++;
		}
	}
	H->Size = n*n;
	BuildHeap(H);
	int ans = 0;
	for (int i = 0; i < n; i++)
	{
		ans += Deletemin(H);
	}
	printf("%d
", ans); }

좋은 웹페이지 즐겨찾기