include stdio include stdlib include string define queue struct Queue

  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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define queue struct Queue
#define Heap struct HEAP
struct HEAP {
int index,k,u;
};
struct Queue {
Heap* heap;
int cap,count;
};
queue Init (int n) {
queue q;
q.heap=(Heap*)malloc(n*sizeof(Heap));
q.cap=n;
q.count=0;
return q;
}
int Empty (queue *q) {
return (q->count==0);
}
void Insert (queue *q, Heap x) {
int i=q->count;
Heap vsp;
q->count++;
q->heap[i]=x;
while (i>0 && (q->heap[(i-1)/2].k < q->heap[i].k)) {
vsp=q->heap[(i-1)/2];
q->heap[(i-1)/2]=q->heap[i];
q->heap[i]=vsp;
q->heap[i].index=i;
i=(i-1)/2;
}
q->heap[i].index=i;
}
void Heapify (Heap *P, int i, int n) {
int l,r,j;
Heap vsp;
while (1) {
l=2*i+1;
r=l+1;
j=i;
if (l<n && P[i].k<P[l].k) i=l;
if (r<n && P[i].k<P[r].k) i=r;
if (i==j) break;
vsp=P[i];
P[i]=P[j];
P[j]=vsp;
P[i].index=i;
P[j].index=j;
}
}
Heap ExtractMax (queue *q) {
Heap ptr=q->heap[0];
q->count--;
if (q->count>0) {
q->heap[0]=q->heap[q->count];
q->heap[0].index=0;
Heapify(q->heap,0,q->count);
}
return ptr;
}
void main () {
int n,i,j,z=0,len=0,max=0;
queue q;
Heap x;
scanf("%d",&n);
int *k=(int*)malloc(n*sizeof(int));
for (i=0;i<n;i++) {
scanf("%d",&k[i]);
if (max<k[i]) max=k[i];
len+=k[i];
}
q=Init(len);
int **Matr=(int**)malloc(n*sizeof(int*));
for (i=0;i<n;i++) Matr[i]=(int*)malloc(max*sizeof(int));
for (i=0;i<n;i++)
for (j=0;j<k[i];j++,z++) {
scanf("%d", &Matr[i][j]);
x.k=Matr[i][j];
x.index=z;
Insert(&q,x);
}
int *Sort=(int*)malloc(len*sizeof(int));
for (i=len-1;i>=0;i--) Sort[i]=ExtractMax(&q).k;
for (i=0;i<len;i++) printf("%d ",Sort[i]);
for (i=0;i<n;i++) free(Matr[i]);
free(Matr);
free(k);
free(Sort);
free(q.heap);
}