4
Copyright (C) 2007 Gabor Csardi <csardi@rmki.kfki.hu>
5
MTA RMKI, Konkoly-Thege Miklos st. 29-33, Budapest 1121, Hungary
7
This program is free software; you can redistribute it and/or modify
8
it under the terms of the GNU General Public License as published by
9
the Free Software Foundation; either version 2 of the License, or
10
(at your option) any later version.
12
This program is distributed in the hope that it will be useful,
13
but WITHOUT ANY WARRANTY; without even the implied warranty of
14
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15
GNU General Public License for more details.
17
You should have received a copy of the GNU General Public License
18
along with this program; if not, write to the Free Software
19
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
30
#include <string.h> /* memcpy & co. */
33
#define PARENT(x) (((x)+1)/2-1)
34
#define LEFTCHILD(x) (((x)+1)*2-1)
35
#define RIGHTCHILD(x) (((x)+1)*2)
39
* \function igraph_heap_init
40
* \brief Initializes an empty heap object.
42
* Creates an empty heap, but allocates size for some elements.
43
* \param h Pointer to an uninitialized heap object.
44
* \param alloc_size Number of elements to allocate memory for.
47
* Time complexity: O(\p alloc_size), assuming memory allocation is a
51
int FUNCTION(igraph_heap,init)(TYPE(igraph_heap)* h, long int alloc_size) {
52
if (alloc_size <= 0 ) { alloc_size=1; }
53
h->stor_begin=igraph_Calloc(alloc_size, BASE);
54
if (h->stor_begin==0) {
55
IGRAPH_ERROR("heap init failed", IGRAPH_ENOMEM);
57
h->stor_end=h->stor_begin + alloc_size;
66
* \function igraph_heap_init_array
67
* \brief Build a heap from an array.
69
* Initializes a heap object from an array, the heap is also
70
* built of course (constructor).
71
* \param h Pointer to an uninitialized heap object.
72
* \param data Pointer to an array of base data type.
73
* \param len The length of the array at \p data.
76
* Time complexity: O(n), the number of elements in the heap.
79
int FUNCTION(igraph_heap,init_array)(TYPE(igraph_heap) *h, BASE* data, long int len) {
80
h->stor_begin=igraph_Calloc(len, BASE);
81
if (h->stor_begin==0) {
82
IGRAPH_ERROR("heap init from array failed", IGRAPH_ENOMEM);
84
h->stor_end=h->stor_begin+len;
88
memcpy(h->stor_begin, data, len*sizeof(igraph_real_t));
90
FUNCTION(igraph_heap,i_build) (h->stor_begin, h->end-h->stor_begin, 0);
97
* \function igraph_heap_destroy
98
* \brief Destroys an initialized heap object.
100
* \param h The heap object.
102
* Time complexity: O(1).
105
void FUNCTION(igraph_heap,destroy)(TYPE(igraph_heap)* h) {
107
if (h->stor_begin != 0) {
108
igraph_Free(h->stor_begin);
116
* \function igraph_heap_empty
117
* \brief Decides whether a heap object is empty.
119
* \param h The heap object.
120
* \return \c TRUE if the heap is empty, \c FALSE otherwise.
122
* TIme complexity: O(1).
125
igraph_bool_t FUNCTION(igraph_heap,empty)(TYPE(igraph_heap)* h) {
127
assert(h->stor_begin != NULL);
128
return h->stor_begin == h->end;
133
* \function igraph_heap_push
134
* \brief Add an element.
136
* Adds an element to the heap.
137
* \param h The heap object.
138
* \param elem The element to add.
139
* \return Error code.
141
* Time complexity: O(log n), n is the number of elements in the
142
* heap if no reallocation is needed, O(n) otherwise. It is ensured
143
* that n push operations are performed in O(n log n) time.
146
int FUNCTION(igraph_heap,push)(TYPE(igraph_heap)* h, BASE elem) {
148
assert(h->stor_begin != NULL);
150
/* full, allocate more storage */
151
if (h->stor_end == h->end) {
152
long int new_size = FUNCTION(igraph_heap,size)(h) * 2;
153
if (new_size == 0) { new_size = 1; }
154
IGRAPH_CHECK(FUNCTION(igraph_heap,reserve)(h, new_size));
161
FUNCTION(igraph_heap,i_shift_up)(h->stor_begin, FUNCTION(igraph_heap,size)(h),
162
FUNCTION(igraph_heap,size)(h)-1);
169
* \function igraph_heap_top
170
* \brief Top element.
172
* For maximum heaps this is the largest, for minimum heaps the
173
* smallest element of the heap.
174
* \param h The heap object.
175
* \return The top element.
177
* Time complexity: O(1).
180
BASE FUNCTION(igraph_heap,top)(TYPE(igraph_heap)* h) {
182
assert(h->stor_begin != NULL);
183
assert(h->stor_begin != h->end);
185
return h->stor_begin[0];
190
* \function igraph_heap_delete_top
191
* \brief Return and removes the top element
193
* Removes and returns the top element of the heap. For maximum heaps
194
* this is the largest, for minimum heaps the smallest element.
195
* \param h The heap object.
196
* \return The top element.
198
* Time complexity: O(log n), n is the number of elements in the
202
BASE FUNCTION(igraph_heap,delete_top)(TYPE(igraph_heap)* h) {
206
assert(h->stor_begin != NULL);
208
tmp=h->stor_begin[0];
209
FUNCTION(igraph_heap,i_switch)(h->stor_begin, 0, FUNCTION(igraph_heap,size)(h)-1);
211
FUNCTION(igraph_heap,i_sink)(h->stor_begin, h->end-h->stor_begin, 0);
218
* \function igraph_heap_size
219
* \brief Number of elements
221
* Gives the number of elements in a heap.
222
* \param h The heap object.
223
* \return The number of elements in the heap.
225
* Time complexity: O(1).
228
long int FUNCTION(igraph_heap,size)(TYPE(igraph_heap)* h) {
230
assert(h->stor_begin != NULL);
231
return h->end - h->stor_begin;
236
* \function igraph_heap_reserve
237
* \brief Allocate more memory
239
* Allocates memory for future use. The size of the heap is
240
* unchanged. If the heap is larger than the \p size parameter then
242
* \param h The heap object.
243
* \param size The number of elements to allocate memory for.
244
* \return Error code.
246
* Time complexity: O(\p size) if \p size is larger than the current
247
* number of elements. O(1) otherwise.
250
int FUNCTION(igraph_heap,reserve)(TYPE(igraph_heap)* h, long int size) {
251
long int actual_size=FUNCTION(igraph_heap,size)(h);
254
assert(h->stor_begin != NULL);
256
if (size <= actual_size) { return 0; }
258
tmp=igraph_Realloc(h->stor_begin, size, BASE);
260
IGRAPH_ERROR("heap reserve failed", IGRAPH_ENOMEM);
263
h->stor_end=h->stor_begin + size;
264
h->end=h->stor_begin+actual_size;
271
* \brief Build a heap, this should not be called directly.
274
void FUNCTION(igraph_heap,i_build)(BASE* arr,
275
long int size, long int head) {
277
if (RIGHTCHILD(head) < size) {
279
FUNCTION(igraph_heap,i_build)(arr, size, LEFTCHILD(head) );
280
FUNCTION(igraph_heap,i_build)(arr, size, RIGHTCHILD(head));
281
FUNCTION(igraph_heap,i_sink)(arr, size, head);
282
} else if (LEFTCHILD(head) < size) {
284
FUNCTION(igraph_heap,i_build)(arr, size, LEFTCHILD(head));
285
FUNCTION(igraph_heap,i_sink)(arr, size, head);
293
* \brief Shift an element upwards in a heap, this should not be
297
void FUNCTION(igraph_heap,i_shift_up)(BASE* arr, long int size, long int elem) {
299
if (elem==0 || arr[elem] HEAPLESS arr[PARENT(elem)]) {
302
FUNCTION(igraph_heap,i_switch)(arr, elem, PARENT(elem));
303
FUNCTION(igraph_heap,i_shift_up)(arr, size, PARENT(elem));
309
* \brief Moves an element down in a heap, this function should not be
313
void FUNCTION(igraph_heap,i_sink)(BASE* arr, long int size, long int head) {
315
if (LEFTCHILD(head) >= size) {
317
} else if (RIGHTCHILD(head) == size ||
318
arr[LEFTCHILD(head)] HEAPMOREEQ arr[RIGHTCHILD(head)]) {
319
/* sink to the left if needed */
320
if (arr[head] HEAPLESS arr[LEFTCHILD(head)]) {
321
FUNCTION(igraph_heap,i_switch)(arr, head, LEFTCHILD(head));
322
FUNCTION(igraph_heap,i_sink)(arr, size, LEFTCHILD(head));
325
/* sink to the right */
326
if (arr[head] HEAPLESS arr[RIGHTCHILD(head)]) {
327
FUNCTION(igraph_heap,i_switch)(arr, head, RIGHTCHILD(head));
328
FUNCTION(igraph_heap,i_sink)(arr, size, RIGHTCHILD(head));
335
* \brief Switches two elements in a heap, this function should not be
339
void FUNCTION(igraph_heap,i_switch)(BASE* arr, long int e1, long int e2) {
added
removed
src/heap.pmt
