Advertisement
Guest User

Untitled

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