Advertisement
informaticage

Heap sort c

Nov 6th, 2020
2,008
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.15 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <stdbool.h>
  4.  
  5. void swap(double *u, double *v);
  6. void fix_heap(double *V, size_t node, size_t N);
  7. size_t heap_right(size_t index, size_t N);
  8. size_t heap_left(size_t index, size_t N);
  9. size_t parent(size_t index);
  10. bool is_leaf(size_t index, size_t N);
  11. void heapify(double *V, size_t node, size_t N);
  12.  
  13. int main(void)
  14. {
  15.     size_t N;
  16.     scanf("%zu", &N);
  17.     double *V = (double *)malloc(sizeof(double) * N);
  18.  
  19.     for (size_t i = 0; i < N; i++)
  20.         scanf("%ld", &V[i]);
  21.  
  22.     fix_heap(V, 0, N);
  23.     printf("[ ");
  24.     for (size_t i = 0; i < N; i++)
  25.         printf("%ld ", V[i]);
  26.     printf("]");
  27.  
  28.     free(V);
  29.     return 0;
  30. }
  31.  
  32. void swap(double *u, double *v)
  33. {
  34.     double temp = *u;
  35.     *u = *v;
  36.     *v = temp;
  37. }
  38.  
  39. size_t heap_left(size_t index, size_t N)
  40. {
  41.     const size_t left = 2 * index + 1;
  42.     return left < N ? left : -1;
  43. }
  44.  
  45. size_t heap_right(size_t index, size_t N)
  46. {
  47.     const size_t right = 2 * index + 2;
  48.     return right < N ? right : -1;
  49. }
  50.  
  51. size_t parent(size_t index)
  52. {
  53.     return (index - 1) / 2;
  54. }
  55.  
  56. bool is_leaf(size_t index, size_t N)
  57. {
  58.     return heap_left(index, N) != -1;
  59. }
  60.  
  61. void fix_heap(double *V, size_t node, size_t N)
  62. {
  63.     // Exit if the node is a leaf
  64.     if (is_leaf(node, N))
  65.         return;
  66.  
  67.     // Largest children of node
  68.     size_t largest;
  69.     size_t left = heap_left(node, N),
  70.            right = heap_right(node, N);
  71.  
  72.     if (left == -1 || right == -1)
  73.         return;
  74.  
  75.     if (V[left] >= V[right])
  76.         largest = left;
  77.     else
  78.         largest = right;
  79.  
  80.     // If son has a larger value swaps pushing the highest value top
  81.     if (V[node] < V[largest])
  82.     {
  83.         // Swap
  84.         swap(&V[node], &V[largest]);
  85.         // Recursion
  86.         fix_heap(V, largest, N);
  87.     }
  88. }
  89.  
  90. void heapify(double *V, size_t node, size_t N)
  91. {
  92.     // If we are done with the heap then return
  93.     if (node == N || node == -1)
  94.         return;
  95.  
  96.     // Right and left recursive heapify
  97.     heapify(V, heap_left(node, N), N);
  98.     heapify(V, heap_right(node, N), N);
  99.  
  100.     // Positioning correctly the root with fixHeap
  101.     fix_heap(V, node, N);
  102. }
  103.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement