diff options
| -rw-r--r-- | heap.c | 30 |
1 files changed, 15 insertions, 15 deletions
| @@ -13,7 +13,7 @@ typedef int T; | |||
| 13 | #define PARENT(idx) ((idx - 1) / 2) | 13 | #define PARENT(idx) ((idx - 1) / 2) |
| 14 | 14 | ||
| 15 | static void | 15 | static void |
| 16 | swap(T heap[], int i, int j) | 16 | swap(T heap[], size_t i, size_t j) |
| 17 | { | 17 | { |
| 18 | T temp = heap[i]; | 18 | T temp = heap[i]; |
| 19 | heap[i] = heap[j]; | 19 | heap[i] = heap[j]; |
| @@ -21,9 +21,9 @@ swap(T heap[], int i, int j) | |||
| 21 | } | 21 | } |
| 22 | 22 | ||
| 23 | static void | 23 | static void |
| 24 | fixup(T heap[], int i) | 24 | fixup(T heap[], size_t i) |
| 25 | { | 25 | { |
| 26 | int p = PARENT(i); | 26 | size_t p = PARENT(i); |
| 27 | 27 | ||
| 28 | while ( i > 0 && heap[p] < heap[i] ) { | 28 | while ( i > 0 && heap[p] < heap[i] ) { |
| 29 | swap(heap, i, p); | 29 | swap(heap, i, p); |
| @@ -34,12 +34,12 @@ fixup(T heap[], int i) | |||
| 34 | } | 34 | } |
| 35 | 35 | ||
| 36 | static void | 36 | static void |
| 37 | fixdown(T heap[], int i, int n) | 37 | fixdown(T heap[], size_t i, size_t n) |
| 38 | { | 38 | { |
| 39 | for ( ;; ) { | 39 | for ( ;; ) { |
| 40 | const int l = LEFT(i); | 40 | const size_t l = LEFT(i); |
| 41 | const int r = RIGHT(i); | 41 | const size_t r = RIGHT(i); |
| 42 | int m = i; | 42 | size_t m = i; |
| 43 | 43 | ||
| 44 | if ( l < n && heap[m] < heap[l] ) | 44 | if ( l < n && heap[m] < heap[l] ) |
| 45 | m = l; | 45 | m = l; |
| @@ -57,18 +57,18 @@ fixdown(T heap[], int i, int n) | |||
| 57 | } | 57 | } |
| 58 | 58 | ||
| 59 | static void | 59 | static void |
| 60 | heapify(T heap[], int n) | 60 | heapify(T heap[], size_t n) |
| 61 | { | 61 | { |
| 62 | for ( int i = n / 2 - 1; i >= 0; --i ) | 62 | for ( size_t i = n / 2 - 1; i >= 0; --i ) |
| 63 | fixdown(heap, i, n); | 63 | fixdown(heap, i, n); |
| 64 | } | 64 | } |
| 65 | 65 | ||
| 66 | static void | 66 | static void |
| 67 | my_heapsort(T a[], int n) | 67 | my_heapsort(T a[], size_t n) |
| 68 | { | 68 | { |
| 69 | heapify(a, n); | 69 | heapify(a, n); |
| 70 | 70 | ||
| 71 | for ( int i = n - 1; i >= 0; --i ) { | 71 | for ( size_t i = n - 1; i >= 0; --i ) { |
| 72 | swap(a, 0, i); | 72 | swap(a, 0, i); |
| 73 | fixdown(a, 0, i); | 73 | fixdown(a, 0, i); |
| 74 | } | 74 | } |
| @@ -77,8 +77,8 @@ my_heapsort(T a[], int n) | |||
| 77 | // ------------------------------------------- | 77 | // ------------------------------------------- |
| 78 | 78 | ||
| 79 | struct pq { // Priority Queue | 79 | struct pq { // Priority Queue |
| 80 | T heap[251]; | 80 | T heap[251]; |
| 81 | int sz; | 81 | size_t sz; |
| 82 | }; | 82 | }; |
| 83 | 83 | ||
| 84 | void | 84 | void |
| @@ -115,11 +115,11 @@ pq_pop(struct pq *pq, T *data) | |||
| 115 | // ------------------------------------------- | 115 | // ------------------------------------------- |
| 116 | 116 | ||
| 117 | void | 117 | void |
| 118 | print_heap(T heap[], int n) | 118 | print_heap(T heap[], size_t n) |
| 119 | { | 119 | { |
| 120 | if ( n ) { | 120 | if ( n ) { |
| 121 | printf("%d", heap[0]); | 121 | printf("%d", heap[0]); |
| 122 | for ( int i = 1; i != n; ++i ) | 122 | for ( size_t i = 1; i != n; ++i ) |
| 123 | printf(", %d", heap[i]); | 123 | printf(", %d", heap[i]); |
| 124 | putchar('\n'); | 124 | putchar('\n'); |
| 125 | } | 125 | } |
