1 /**CFile***********************************************************************
7 Synopsis [Functions for heap-based priority queue.]
9 Description [The functions in this file manage a priority queue implemented
10 as a heap. The first element of the heap is the one with the smallest key.
11 Refer to Chapter 7 of Cormen, Leiserson, and Rivest for the theory.]
15 Author [Fabio Somenzi]
17 Copyright [Copyright (c) 1995-2004, Regents of the University of Colorado
21 Redistribution and use in source and binary forms, with or without
22 modification, are permitted provided that the following conditions
25 Redistributions of source code must retain the above copyright
26 notice, this list of conditions and the following disclaimer.
28 Redistributions in binary form must reproduce the above copyright
29 notice, this list of conditions and the following disclaimer in the
30 documentation and/or other materials provided with the distribution.
32 Neither the name of the University of Colorado nor the names of its
33 contributors may be used to endorse or promote products derived from
34 this software without specific prior written permission.
36 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
37 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
38 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
39 FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
40 COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
41 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
42 BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
43 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
44 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
45 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
46 ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
47 POSSIBILITY OF SUCH DAMAGE.]
49 ******************************************************************************/
53 /*---------------------------------------------------------------------------*/
54 /* Constant declarations */
55 /*---------------------------------------------------------------------------*/
58 /*---------------------------------------------------------------------------*/
59 /* Stucture declarations */
60 /*---------------------------------------------------------------------------*/
62 /*---------------------------------------------------------------------------*/
63 /* Type declarations */
64 /*---------------------------------------------------------------------------*/
66 /*---------------------------------------------------------------------------*/
67 /* Variable declarations */
68 /*---------------------------------------------------------------------------*/
71 static char rcsid
[] UTIL_UNUSED
= "$Id: ntrHeap.c,v 1.5 2004/08/13 18:28:28 fabio Exp fabio $";
74 /*---------------------------------------------------------------------------*/
75 /* Macro declarations */
76 /*---------------------------------------------------------------------------*/
78 #define PARENT(i) (((i)-1)>>1)
79 #define RIGHT(i) (((i)+1)<<1)
80 #define LEFT(i) (((i)<<1)|1)
81 #define ITEM(p,i) ((p)[i].item)
82 #define KEY(p,i) ((p)[i].key)
84 /**AutomaticStart*************************************************************/
86 /*---------------------------------------------------------------------------*/
87 /* Static function prototypes */
88 /*---------------------------------------------------------------------------*/
90 static void ntrHeapify (NtrHeap
*heap
, int i
);
91 static int ntrHeapResize (NtrHeap
*heap
);
93 /**AutomaticEnd***************************************************************/
95 /*---------------------------------------------------------------------------*/
96 /* Definition of exported functions */
97 /*---------------------------------------------------------------------------*/
100 /**Function********************************************************************
102 Synopsis [Initializes a priority queue.]
104 Description [Initializes a priority queue. Returns a pointer to the heap
105 if successful; NULL otherwise.]
109 SeeAlso [Ntr_FreeHeap]
111 ******************************************************************************/
118 heap
= ALLOC(NtrHeap
,1);
119 if (heap
== NULL
) return(NULL
);
122 heap
->slots
= ALLOC(NtrHeapSlot
,size
);
123 if (heap
->slots
== NULL
) {
129 } /* end of Ntr_InitHeap */
132 /**Function********************************************************************
134 Synopsis [Frees a priority queue.]
140 SeeAlso [Ntr_InitHeap]
142 ******************************************************************************/
151 } /* end of Ntr_FreeHeap */
154 /**Function********************************************************************
156 Synopsis [Inserts an item in a priority queue.]
158 Description [Inserts an item in a priority queue. Returns 1 if successful;
163 SeeAlso [Ntr_HeapExtractMin]
165 ******************************************************************************/
173 int i
= heap
->nslots
;
175 if (i
== heap
->size
&& !ntrHeapResize(heap
)) return(0);
178 while (i
> 0 && KEY(slots
,PARENT(i
)) > key
) {
179 ITEM(slots
,i
) = ITEM(slots
,PARENT(i
));
180 KEY(slots
,i
) = KEY(slots
,PARENT(i
));
183 ITEM(slots
,i
) = item
;
187 } /* end of Ntr_HeapInsert */
190 /**Function********************************************************************
192 Synopsis [Extracts the element with the minimum key from a priority
195 Description [Extracts the element with the minimum key from a priority
196 queue. Returns 1 if successful; 0 otherwise.]
198 SideEffects [The minimum key and the associated item are returned as
201 SeeAlso [Ntr_HeapInsert]
203 ******************************************************************************/
210 NtrHeapSlot
*slots
= heap
->slots
;
212 if (heap
->nslots
== 0) return(0);
213 *(void **)item
= ITEM(slots
,0);
216 ITEM(slots
,0) = ITEM(slots
,heap
->nslots
);
217 KEY(slots
,0) = KEY(slots
,heap
->nslots
);
222 } /* end of Ntr_HeapExtractMin */
225 /**Function********************************************************************
227 Synopsis [Returns the number of items in a priority queue.]
235 ******************************************************************************/
240 return(heap
->nslots
);
242 } /* end of Ntr_HeapCount */
245 /**Function********************************************************************
247 Synopsis [Clones a priority queue.]
253 SeeAlso [Ntr_InitHeap]
255 ******************************************************************************/
262 int nslots
= source
->nslots
;
263 NtrHeapSlot
*sslots
= source
->slots
;
266 dest
= Ntr_InitHeap(source
->size
);
267 if (dest
== NULL
) return(NULL
);
268 dest
->nslots
= nslots
;
269 dslots
= dest
->slots
;
270 for (i
= 0; i
< nslots
; i
++) {
271 KEY(dslots
,i
) = KEY(sslots
,i
);
272 ITEM(dslots
,i
) = ITEM(sslots
,i
);
276 } /* end of Ntr_HeapClone */
279 /**Function********************************************************************
281 Synopsis [Tests the heap property of a priority queue.]
283 Description [Tests the heap property of a priority queue. Returns 1 if
284 Successful; 0 otherwise.]
290 ******************************************************************************/
296 NtrHeapSlot
*slots
= heap
->slots
;
297 int nslots
= heap
->nslots
;
299 if (i
> 0 && KEY(slots
,i
) < KEY(slots
,PARENT(i
)))
301 if (LEFT(i
) < nslots
) {
302 if (!Ntr_TestHeap(heap
,LEFT(i
)))
305 if (RIGHT(i
) < nslots
) {
306 if (!Ntr_TestHeap(heap
,RIGHT(i
)))
311 } /* end of Ntr_TestHeap */
314 /*---------------------------------------------------------------------------*/
315 /* Definition of static functions */
316 /*---------------------------------------------------------------------------*/
319 /**Function********************************************************************
321 Synopsis [Maintains the heap property of a priority queue.]
327 SeeAlso [Ntr_HeapExtractMin]
329 ******************************************************************************/
337 int right
= RIGHT(i
);
338 int nslots
= heap
->nslots
;
339 NtrHeapSlot
*slots
= heap
->slots
;
340 int key
= KEY(slots
,i
);
342 if (left
< nslots
&& KEY(slots
,left
) < key
) {
347 if (right
< nslots
&& KEY(slots
,right
) < KEY(slots
,smallest
)) {
351 void *item
= ITEM(slots
,i
);
352 KEY(slots
,i
) = KEY(slots
,smallest
);
353 ITEM(slots
,i
) = ITEM(slots
,smallest
);
354 KEY(slots
,smallest
) = key
;
355 ITEM(slots
,smallest
) = item
;
356 ntrHeapify(heap
,smallest
);
361 } /* end of ntrHeapify */
364 /**Function********************************************************************
366 Synopsis [Resizes a priority queue.]
368 Description [Resizes a priority queue by doubling the number of
369 available slots. Returns 1 if successful; 0 otherwise.]
373 SeeAlso [Ntr_HeapInsert]
375 ******************************************************************************/
380 int oldlength
= heap
->size
;
381 int newlength
= 2 * oldlength
;
382 NtrHeapSlot
*oldslots
= heap
->slots
;
383 NtrHeapSlot
*newslots
= REALLOC(NtrHeapSlot
, oldslots
, newlength
);
384 if (newslots
== NULL
) return 0;
385 heap
->size
= newlength
;
386 heap
->slots
= newslots
;
387 assert(Ntr_TestHeap(heap
, 0));
390 } /* end of ntrHeapResize */