Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- typedef struct Priority {
- int *heap;
- int cap;
- int count;
- }queue;
- void InitPriorityQueue(queue *q, int n) {
- q->heap = malloc(n * sizeof(int));
- q->cap = n;
- q->count = 0;
- }
- int QueueEmpty(queue *q) {
- return (q->count == 0);
- }
- void Insert(queue *q, int ptr){
- int i = q->count, t = 0;
- if (i == q->cap)
- printf("error");
- q->count = i + 1;
- q->heap[i] = ptr;
- while ((i > 0) && (q->heap[(i - 1) / 2] > q->heap[i])) {
- t = q->heap[(i - 1) / 2];
- q->heap[(i - 1) / 2] = q->heap[i];
- q->heap[i] = t;
- i = (i - 1) / 2;
- }
- }
- int ExtractMax(queue *q) {
- int i = 0, j = 0, ptr = q->heap[0], t = 0;
- if (QueueEmpty(q))
- printf("The queue is empty.");
- q->count--;
- q->heap[0] = q->heap[q->count];
- while (i < q->count / 2) {
- j = 2 * i + 1;
- if ((j < q->count) && (q->heap[j + 1] < q->heap[j]))
- j++;
- if (q->heap[i] <= q->heap[j])
- return ptr;
- t = q->heap[j];
- q->heap[j] = q->heap[i];
- q->heap[i] = t;
- i = j;
- }
- return ptr;
- }
- int main() {
- int i = 0, k = 0, n = 0, summ = 0;
- scanf("%d", &n);
- for (i = 0; i < n; i++){
- scanf("%d", &k);
- summ += k;
- }
- queue qu;
- queue *q = &qu;
- InitPriorityQueue(q, summ);
- for (i = 0; i < summ; i++){
- scanf("%d", &k);
- Insert(q, k);
- }
- for (i = 0; i < summ; i++){
- printf("%d ", ExtractMax(q));
- }
- free(q->heap);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement