| 67 | } |
| 68 | |
| 69 | void sortDecreasingHeap(const HighsInt n, vector<double>& heap_v, |
| 70 | vector<HighsInt>& heap_ix) { |
| 71 | HighsInt fo_p, srt_p; |
| 72 | HighsInt cd_p, pa_p; |
| 73 | HighsInt ix; |
| 74 | double v; |
| 75 | if (n <= 1) return; |
| 76 | if (heap_ix[0] != 1) { |
| 77 | // The data are assumed to be completely unordered. A heap will be formed |
| 78 | // and sorted. |
| 79 | fo_p = n / 2 + 1; |
| 80 | srt_p = n; |
| 81 | } else { |
| 82 | // The data are assumed to form a heap which is to be sorted. |
| 83 | fo_p = 1; |
| 84 | srt_p = n; |
| 85 | } |
| 86 | for (;;) { |
| 87 | if (fo_p > 1) { |
| 88 | fo_p = fo_p - 1; |
| 89 | v = heap_v[fo_p]; |
| 90 | ix = heap_ix[fo_p]; |
| 91 | } else { |
| 92 | v = heap_v[srt_p]; |
| 93 | ix = heap_ix[srt_p]; |
| 94 | heap_v[srt_p] = heap_v[1]; |
| 95 | heap_ix[srt_p] = heap_ix[1]; |
| 96 | srt_p--; |
| 97 | if (srt_p == 1) { |
| 98 | heap_v[1] = v; |
| 99 | heap_ix[1] = ix; |
| 100 | return; |
| 101 | } |
| 102 | } |
| 103 | pa_p = fo_p; |
| 104 | cd_p = fo_p + fo_p; |
| 105 | for (;;) { |
| 106 | if (cd_p <= srt_p) { |
| 107 | if (cd_p < srt_p) { |
| 108 | if (heap_v[cd_p] > heap_v[cd_p + 1]) cd_p = cd_p + 1; |
| 109 | } |
| 110 | if (v > heap_v[cd_p]) { |
| 111 | heap_v[pa_p] = heap_v[cd_p]; |
| 112 | heap_ix[pa_p] = heap_ix[cd_p]; |
| 113 | pa_p = cd_p; |
| 114 | cd_p = cd_p + cd_p; |
| 115 | continue; |
| 116 | } |
| 117 | } |
| 118 | break; |
| 119 | } |
| 120 | heap_v[pa_p] = v; |
| 121 | heap_ix[pa_p] = ix; |
| 122 | } |
| 123 | return; |
| 124 | } |
| 125 | |
| 126 | void maxheapsort(HighsInt* heap_v, HighsInt n) { |
no outgoing calls