65 lines
No EOL
1.3 KiB
C
65 lines
No EOL
1.3 KiB
C
int printf(char* format, ...);
|
|
int scanf(char* format, ...);
|
|
|
|
// sort by a max heap
|
|
|
|
int heap[100];
|
|
int heap_size = 0;
|
|
|
|
void push_heap(int value) {
|
|
heap[heap_size] = value;
|
|
int i = heap_size;
|
|
heap_size++;
|
|
while (i > 0) {
|
|
int parent = (i - 1) / 2;
|
|
if (heap[i] > heap[parent]) {
|
|
int temp = heap[i];
|
|
heap[i] = heap[parent];
|
|
heap[parent] = temp;
|
|
i = parent;
|
|
} else {
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
|
|
int pop_heap() {
|
|
int value = heap[0];
|
|
heap_size--;
|
|
heap[0] = heap[heap_size];
|
|
int i = 0;
|
|
while (i < heap_size) {
|
|
int left = 2 * i + 1;
|
|
int right = 2 * i + 2;
|
|
if (left >= heap_size) {
|
|
break;
|
|
}
|
|
int max_child = left;
|
|
if (right < heap_size && heap[right] > heap[left]) {
|
|
max_child = right;
|
|
}
|
|
if (heap[i] < heap[max_child]) {
|
|
int temp = heap[i];
|
|
heap[i] = heap[max_child];
|
|
heap[max_child] = temp;
|
|
i = max_child;
|
|
} else {
|
|
break;
|
|
}
|
|
}
|
|
return value;
|
|
}
|
|
|
|
int main() {
|
|
int n;
|
|
scanf("%d", &n);
|
|
for (int i = 0; i < n; i++) {
|
|
int value;
|
|
scanf("%d", &value);
|
|
push_heap(value);
|
|
}
|
|
for (int i = 0; i < n; i++) {
|
|
printf("%d ", pop_heap());
|
|
}
|
|
printf("\n");
|
|
} |