Advertisement
And1

Untitled

Dec 25th, 2018
142
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.59 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. struct queue {
  5.     int *heap;
  6.     int cap, count;
  7. };
  8.  
  9. struct queue initPriorityQueue (int);
  10. void insert(struct queue *, int);
  11. void swapQ(struct queue *, int, int);
  12. int extractMin(struct queue *);
  13.  
  14. int main(int argc, char *argv[]) {
  15.     int n;
  16.     scanf("%d", &n);
  17.     int t;
  18.     int c = 0;
  19.     for (int i = 0; i < n; i++){
  20.         scanf("%d", &t);
  21.         c += t;
  22.     }
  23.     struct queue q = initPriorityQueue(c);
  24.     for (int i = 0; i < c; i++){
  25.         scanf("%d", &t);
  26.         insert(&q, t);
  27.     }
  28.     for (int i = 0; i < c; i++){
  29.         int e = extractMin(&q);
  30.         printf("%d ", e);
  31.     }
  32.     free (q.heap);
  33.     return 0;
  34. }
  35.  
  36. struct queue initPriorityQueue(int n){
  37.     struct queue q;
  38.     q.heap = (int *)malloc(sizeof(int) * n);
  39.     q.cap = n;
  40.     q.count = 0;
  41.     return q;
  42. }
  43.  
  44. void insert (struct queue *q, int k){
  45.     int i = q->count;
  46.     q->count++;
  47.     q->heap[i] = k;
  48.     for (;i > 0 && q->heap[(i - 1) / 2] > q->heap[i]; i = (i - 1) / 2) {
  49.         swapQ(q, i, (i - 1) / 2);
  50.     }
  51. }
  52.  
  53. void swapQ (struct queue *q, int i, int j){
  54.     int t = q->heap[i];
  55.     q->heap[i] = q->heap[j];
  56.     q->heap[j] = t;
  57. }
  58.  
  59. int extractMin(struct queue *q){
  60.     int x = q->heap[0];
  61.     q->count--;
  62.     q->heap[0] = q->heap[q->count];
  63.     for (int i = 0, max; i < q->count / 2;){
  64.         max = ((2 * i + 2 < q->count) && (q->heap[2 * i + 2] < q->heap[2 * i + 1])) ?  (2 * 1 + 2) : (2 * i + 1);
  65.         if (q->heap[i] <= q->heap[max])
  66.             return x;
  67.         swapQ(q, i, max);
  68.         i = max;
  69.     }
  70.     return x;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement