C 언어 는 최대 쌓 기 최소 쌓 기 및 쌓 기 정렬 을 실현 합 니 다.
3658 단어 알고리즘
삽입 작업 은 배열 의 마지막 에 두 고 이 점 의 부모 노드 가 이 삽입 값 보다 크 면
그러면 하위 노드 의 값 을 부모 노드 로 대체 하고 부모 노드 를 계속 위로 비교 하 며 적당 한 위치 로 이동 하여 해당 하 는 값 을 부여 합 니 다.
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);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.