Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- struct queue {
- int *heap;
- int cap, count;
- };
- struct queue initPriorityQueue (int);
- void insert(struct queue *, int);
- void swapQ(struct queue *, int, int);
- int extractMin(struct queue *);
- int main(int argc, char *argv[]) {
- int n;
- scanf("%d", &n);
- int t;
- int c = 0;
- for (int i = 0; i < n; i++){
- scanf("%d", &t);
- c += t;
- }
- struct queue q = initPriorityQueue(c);
- for (int i = 0; i < c; i++){
- scanf("%d", &t);
- insert(&q, t);
- }
- for (int i = 0; i < c; i++){
- int e = extractMin(&q);
- printf("%d ", e);
- }
- free (q.heap);
- return 0;
- }
- struct queue initPriorityQueue(int n){
- struct queue q;
- q.heap = (int *)malloc(sizeof(int) * n);
- q.cap = n;
- q.count = 0;
- return q;
- }
- void insert (struct queue *q, int k){
- int i = q->count;
- q->count++;
- q->heap[i] = k;
- for (;i > 0 && q->heap[(i - 1) / 2] > q->heap[i]; i = (i - 1) / 2) {
- swapQ(q, i, (i - 1) / 2);
- }
- }
- void swapQ (struct queue *q, int i, int j){
- int t = q->heap[i];
- q->heap[i] = q->heap[j];
- q->heap[j] = t;
- }
- int extractMin(struct queue *q){
- int x = q->heap[0];
- q->count--;
- q->heap[0] = q->heap[q->count];
- for (int i = 0, max; i < q->count / 2;){
- max = ((2 * i + 2 < q->count) && (q->heap[2 * i + 2] < q->heap[2 * i + 1])) ? (2 * 1 + 2) : (2 * i + 1);
- if (q->heap[i] <= q->heap[max])
- return x;
- swapQ(q, i, max);
- i = max;
- }
- return x;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement