|
* e) { e->min_heap_idx = -1; }
64 int min_heap_empty(min_heap_t* s) { return 0u == s->n; }
65 unsigned min_heap_size(min_heap_t* s) { return s->n; }
66 struct event* min_heap_top(min_heap_t* s) { return s->n ? *s->p : 0; }
67
68 //插入元素
69 int min_heap_push(min_heap_t* s, struct event* e)
70 {
71 //检查内存
72 if(min_heap_reserve(s, s->n + 1))
73 return -1;
74
75 //插入元素向上调整
76 min_heap_shift_up_(s, s->n++, e);
77 return 0;
78 }
79
80 //pop头元素
81 struct event* min_heap_pop(min_heap_t* s)
82 {
83 if(s->n)
84 {
85 //->优先级比*高
86 //e指向头元素的指针
87 struct event* e = *s->p;
88 //元素向下调整，0U代表头节点索引，s->p[--s->n]：最下层最右边元素，用于插入后填充空出的位置
89 min_heap_shift_down_(s, 0u, s->p[--s->n]);
90
91 //头元素在堆中索引赋值为-1，出堆
92 e->min_heap_idx = -1;
93 return e;
94 }
95 return 0;
96 }
97
98 //删除堆中等于e的元素
99 int min_heap_erase(min_heap_t* s, struct event* e)
100 {
101 if(((unsigned int)-1) != e->min_heap_idx)
102 {
103 struct event *last = s->p[--s->n];
104 //父节点索引
105 unsigned parent = (e->min_heap_idx - 1) / 2;
106 /* we replace e with the last element in the heap. We might need to
107 shift it upward if it is less than its parent, or downward if it is
108 greater than one or both its children. Since the children are known
109 to be less than the parent, it can't need to shift both up and
110 down. */
111 //如果e不是根元素，当前e的父节点值大于last，需要进行向上调整
112 if (e->min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last))
113 min_heap_shift_up_(s, e->min_heap_idx, last);
114 else
115 //如果e是根元素或者e的父节点元素值不大于last，元素向下调整，e->min_heap_idx为头节点索引，last：最下层最右边元素
116 //，用于插入后填充空出的位置
117 min_heap_shift_down_(s, e->min_heap_idx, last);
118 //将e元素出堆
119 e->min_heap_idx = -1;
120 return 0;
121 }
122 return -1;
123 }
124
125 //调整分配内存
126 int min_heap_reserve(min_heap_t* s, unsigned n)
127 {
128 //如果元素的容量小于元素个数，需要重新分配内存
129 if(s->a < n)
130 {
131 struct event** p;
132 //a原来默认为0就分配为8，如果以前有值（不是第一次调整），就扩大两倍
133 unsigned a = s->a ? s->a * 2 : 8;
134 //如果a还不够，直接让a等于n，元素个数和容量相同
135 if(a < n)
136 a = n;
137 //重新调整内存，连续分配
138 if(!(p = (struct event**)realloc(s->p, a * sizeof *p)))
139 return -1;
140 //首地址
141 s->p = p;
142 //容量
143 s->a = a;
144 }
145 return 0;
146 }
147
148 //插入元素后向上调整
149 void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e)
150 {
151 //父节点的索引
152 unsigned parent = (hole_index - 1) / 2;
153 //如果hole_index不等于0且父节点元素大于所给的元素，继续比较，直到到达hole_index为根元素，
154 //或者现在的父元素大于了e，找到插入的位置
155 while(hole_index && min_heap_elem_greater(s->p[parent], e))
156 {
157 //父节点元素值大，将父节点放到现在的hole_index上的位置
158 (s->p[hole_index] = s->p[parent])->min_heap_idx = hole_index;
159
160 //hole_index赋值为父节点的索引
161 hole_index = parent;
162
163 //找到现在的hole_index的父节点索引
164 parent = (hole_index - 1) / 2;
165 }
166
167 //跳出循环找到了要插入的位置，位置的索引就是现在的hole_index
168 (s->p[hole_index] = e)->min_heap_idx = hole_index;
169 }
170
171 //元素向下调整（删除元素）
172 void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e)
173 {
174 //右孩子索引
175 unsigned min_child = 2 * (hole_index + 1);
176 //存在右孩子，如果不存在右子树，直接向下调整，因为最多存在左子树，且值肯定不小于父节点，可以直接向下调整
177 while(min_child <= s->n)
178 {
179 //选择左右孩子值最小的孩子的索引，根据优先级可以加()进行更好的查看
180 min_child -= ((min_child == s->n) || min_heap_elem_greater(s->p[min_child], s->p[min_chil |