include stdio include stdlib struct mas int pos end struct Pqueue int

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <stdio.h>
#include <stdlib.h>
struct mas
{
int *a,pos,end;
};
struct Pqueue
{
int cap,count;
struct mas *h;
};
void InitPqueue(struct Pqueue* pq, int MasCount)
{
pq->h = (struct mas*)malloc(MasCount * sizeof(struct mas));
pq->cap = MasCount;
pq->count = 0;
}
void insert(struct Pqueue *pq,struct mas ptr)
{
int i;
i=pq->count;
pq->count=i+1;
pq->h[i]=ptr;
struct mas Swap;
while(i>0 && pq->h[(i-1)/2].a[0] > pq->h[i].a[0])
{
Swap=pq->h[(i-1)/2];
pq->h[(i-1)/2]=pq->h[i];
pq->h[i]=Swap;
i = (i-1)/2;
}
}
void Heapify(struct Pqueue* pq)
{
int l, r, j,i;
struct mas swap;
for(i = 0;;)
{
l = 2*i+1;
r = l+1;
j = i;
if(l < pq->count && pq->h[l].a[0] < pq->h[j].a[0])
{
j = l;
}
if(r < pq->count && pq->h[r].a[0] < pq->h[j].a[0])
{
j = r;
}
if(i == j)
{
break;
}
swap = pq->h[i];
pq->h[i] = pq->h[j];
pq->h[j] = swap;
i = j;
}
}
void ExtractMax(struct Pqueue *pq)
{
printf("%d ", pq->h[0].a[0] );
struct mas s;
if(pq->h[0].pos < pq->h[0].end)
{
pq->h[0].a++;
pq->h[0].pos++;
}
pq->count-=1;
s=pq->h[0];
pq->h[0]=pq->h[pq->count];
Heapify(pq);
if(s.pos < s.end)
{
insert(pq, s);
}
}
int main (int argc, char const *argv[])
{
int MasCount,i,NumOfElem=0,count,len=0,j;
scanf("%d", &MasCount );
struct Pqueue pq;
InitPqueue(&pq, MasCount);
for(i = 0; i < MasCount; i++)
{
scanf("%d", &count );
NumOfElem+=count;
pq.h[i].end=count;
if(count>len)
{
len=count;
}
}
int m[MasCount][len];
struct mas ptr;
for(i = 0; i < MasCount;i++)
{
for(j = 0; j < pq.h[i].end; j++)
{
scanf("%d", &m[i][j]);
}
if(pq.h[i].end != 0)
{
ptr.a=&m[i][0];
ptr.pos=0;
ptr.end=pq.h[i].end;
insert(&pq,ptr);
}
}
for(i = 0; i < NumOfElem; i++)
{
ExtractMax(&pq);
}
free(pq.h);
return 0;
}