OLD | NEW |
1 /* | 1 /* |
2 * Copyright (c) 2006 Maxim Yegorushkin <maxim.yegorushkin@gmail.com> | 2 * Copyright (c) 2006 Maxim Yegorushkin <maxim.yegorushkin@gmail.com> |
3 * All rights reserved. | 3 * All rights reserved. |
4 * | 4 * |
5 * Redistribution and use in source and binary forms, with or without | 5 * Redistribution and use in source and binary forms, with or without |
6 * modification, are permitted provided that the following conditions | 6 * modification, are permitted provided that the following conditions |
7 * are met: | 7 * are met: |
8 * 1. Redistributions of source code must retain the above copyright | 8 * 1. Redistributions of source code must retain the above copyright |
9 * notice, this list of conditions and the following disclaimer. | 9 * notice, this list of conditions and the following disclaimer. |
10 * 2. Redistributions in binary form must reproduce the above copyright | 10 * 2. Redistributions in binary form must reproduce the above copyright |
(...skipping 68 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
79 e->min_heap_idx = -1; | 79 e->min_heap_idx = -1; |
80 return e; | 80 return e; |
81 } | 81 } |
82 return 0; | 82 return 0; |
83 } | 83 } |
84 | 84 |
85 int min_heap_erase(min_heap_t* s, struct event* e) | 85 int min_heap_erase(min_heap_t* s, struct event* e) |
86 { | 86 { |
87 if(((unsigned int)-1) != e->min_heap_idx) | 87 if(((unsigned int)-1) != e->min_heap_idx) |
88 { | 88 { |
89 min_heap_shift_down_(s, e->min_heap_idx, s->p[--s->n]); | 89 struct event *last = s->p[--s->n]; |
| 90 unsigned parent = (e->min_heap_idx - 1) / 2; |
| 91 » /* we replace e with the last element in the heap. We might need to |
| 92 » shift it upward if it is less than its parent, or downward if it is |
| 93 » greater than one or both its children. Since the children are known |
| 94 » to be less than the parent, it can't need to shift both up and |
| 95 » down. */ |
| 96 if (e->min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last)) |
| 97 min_heap_shift_up_(s, e->min_heap_idx, last); |
| 98 else |
| 99 min_heap_shift_down_(s, e->min_heap_idx, last); |
90 e->min_heap_idx = -1; | 100 e->min_heap_idx = -1; |
91 return 0; | 101 return 0; |
92 } | 102 } |
93 return -1; | 103 return -1; |
94 } | 104 } |
95 | 105 |
96 int min_heap_reserve(min_heap_t* s, unsigned n) | 106 int min_heap_reserve(min_heap_t* s, unsigned n) |
97 { | 107 { |
98 if(s->a < n) | 108 if(s->a < n) |
99 { | 109 { |
(...skipping 30 matching lines...) Expand all Loading... |
130 if(!(min_heap_elem_greater(e, s->p[min_child]))) | 140 if(!(min_heap_elem_greater(e, s->p[min_child]))) |
131 break; | 141 break; |
132 (s->p[hole_index] = s->p[min_child])->min_heap_idx = hole_index; | 142 (s->p[hole_index] = s->p[min_child])->min_heap_idx = hole_index; |
133 hole_index = min_child; | 143 hole_index = min_child; |
134 min_child = 2 * (hole_index + 1); | 144 min_child = 2 * (hole_index + 1); |
135 } | 145 } |
136 min_heap_shift_up_(s, hole_index, e); | 146 min_heap_shift_up_(s, hole_index, e); |
137 } | 147 } |
138 | 148 |
139 #endif /* _MIN_HEAP_H_ */ | 149 #endif /* _MIN_HEAP_H_ */ |
OLD | NEW |