source: trunk/optimizer/src/pgapack/pgapack/source/heap.c @ 816

Last change on this file since 816 was 816, checked in by liveletlive, 16 years ago

Committing the newer version of PGAPack.
File size: 8.4 KB
Line 
1/*
2 * 
3 *  *********************************************************************
4 *  (C) COPYRIGHT 1995 UNIVERSITY OF CHICAGO
5 *  *********************************************************************
6 * 
7 *  This software was authored by
8 * 
9 *  D. Levine
10 *  Mathematics and Computer Science Division Argonne National Laboratory
11 *  Argonne IL 60439
12 *  levine@mcs.anl.gov
13 *  (708) 252-6735
14 *  (708) 252-5986 (FAX)
15 * 
16 *  with programming assistance of participants in Argonne National
17 *  Laboratory's SERS program.
18 * 
19 *  This program contains material protectable under copyright laws of the
20 *  United States.  Permission is hereby granted to use it, reproduce it,
21 *  to translate it into another language, and to redistribute it to
22 *  others at no charge except a fee for transferring a copy, provided
23 *  that you conspicuously and appropriately publish on each copy the
24 *  University of Chicago's copyright notice, and the disclaimer of
25 *  warranty and Government license included below.  Further, permission
26 *  is hereby granted, subject to the same provisions, to modify a copy or
27 *  copies or any portion of it, and to distribute to others at no charge
28 *  materials containing or derived from the material.
29 * 
30 *  The developers of the software ask that you acknowledge its use in any
31 *  document referencing work based on the  program, such as published
32 *  research.  Also, they ask that you supply to Argonne National
33 *  Laboratory a copy of any published research referencing work based on
34 *  the software.
35 * 
36 *  Any entity desiring permission for further use must contact:
37 * 
38 *  J. Gleeson
39 *  Industrial Technology Development Center Argonne National Laboratory
40 *  Argonne IL 60439
41 *  gleesonj@smtplink.eid.anl.gov
42 *  (708) 252-6055
43 * 
44 *  ********************************************************************
45 *  DISCLAIMER
46 * 
47 *  THIS PROGRAM WAS PREPARED AS AN ACCOUNT OF WORK SPONSORED BY AN AGENCY
48 *  OF THE UNITED STATES GOVERNMENT.  NEITHER THE UNIVERSITY OF CHICAGO,
49 *  THE UNITED STATES GOVERNMENT NOR ANY OF THEIR EMPLOYEES MAKE ANY
50 *  WARRANTY, EXPRESS OR IMPLIED, OR ASSUMES ANY LEGAL LIABILITY OR
51 *  RESPONSIBILITY FOR THE ACCURACY, COMPLETENESS, OR USEFULNESS OF ANY
52 *  INFORMATION OR PROCESS DISCLOSED, OR REPRESENTS THAT ITS USE WOULD NOT
53 *  INFRINGE PRIVATELY OWNED RIGHTS.
54 * 
55 *  **********************************************************************
56 *  GOVERNMENT LICENSE
57 * 
58 *  The Government is granted for itself and others acting on its behalf a
59 *  paid-up, non-exclusive, irrevocable worldwide license in this computer
60 *  software to reproduce, prepare derivative works, and perform publicly
61 *  and display publicly.
62 */
63
64/*****************************************************************************
65*      FILE: heap.c: This file contains routines for sorting individuals for
66*                     selection
67*
68*      Authors: David M. Levine, Philip L. Hallstrom, David M. Noelle,
69*               Brian P. Walenz
70*****************************************************************************/
71
72#include <pgapack.h>
73
74/******************************************************************************
75   PGAAdjustHeap - Auxiliary routine called by PGA*HeapSort
76
77   Category: Sorting
78
79   Inputs:
80       ctx      - context variable
81       a        - array of values to be sorted
82       idx      - array of integer indices corresponding to the array
83                  a being sorted
84       i        - point of combination -- combine the node at a[i] with
85                  the two heaps at a[2i+1] and a[2i+2] to form a single
86                  heap.  0 <= i <= n-1.
87       n        - size of the arrays a and idx
88       j        - temporary variable, integer
89       item     - temporary variable, type must be same as a
90       item_idx - temporary variable, integer
91
92   Output:
93
94   Example:
95
96******************************************************************************/
97#define PGAAdjustHeap(ctx, a, idx, i, n, j, item, item_idx) {       \
98  item     = a[i];                                                  \
99  item_idx = idx[i];                                                \
100  j = 2*i+1;      /* let j be the left child */                     \
101  while (j < n) {                                                   \
102    if (j<n-1 && a[j] > a[j+1])                                     \
103       j = j + 1;       /* j is the larger child */                 \
104    if (item <= a[j])   /* a position for item has been found */    \
105       break;                                                       \
106    a[(j-1)/2]   = a[j];    /* move the larger child up a level */  \
107    idx[(j-1)/2] = idx[j];                                          \
108    j = j*2+1;                                                      \
109  }                                                                 \
110  a[(j-1)/2]   = item;                                              \
111  idx[(j-1)/2] = item_idx;                                          \
112}                                                                   \
113
114
115
116
117/*I****************************************************************************
118   PGADblHeapSort - Uses a heapsort algorithm to sort from largest to smallest
119   element.  An integer array, intialized with the original indices of the
120   elements of array a is sorted also so that the original locations are known
121
122   Category: Sorting
123
124   Inputs:
125       ctx      - context variable
126       a        - array of (double) values to be sorted
127       idx      - array of integer indices corresponding to the array
128                  a being sorted
129       n        - size of the arrays a and idx
130
131   Output:
132       The sorted arrays a and idx
133
134   Example:
135      The following code sorts the population by fitness
136
137      PGAContext *ctx;
138      int i,j,n,idx[LARGE]
139      double a[LARGE];
140      :
141      n = PGAGetPopsize(ctx);
142      for(i=0;i<n;i++) {
143        a[i]   = PGAGetFitness(ctx,p,PGA_OLDPOP);
144        idx[i] = i;
145      }
146      PGADblHeapSort ( ctx, a, idx, n);
147
148****************************************************************************I*/
149void PGADblHeapSort ( PGAContext *ctx, double *a, int *idx, int n )
150{
151  int i;
152  double temp_a;
153  int temp_idx;
154  int j, item_idx;
155  double item;
156
157    PGADebugEntered("PGADblHeapSort");
158
159  /*  Create a heap from our array  */
160  for (i=(n-2)/2; i>=0; i--)
161    PGAAdjustHeap(ctx, a, idx, i, n, j, item, item_idx);
162
163  for ( i=n-1; i>=1; i--)  /* interchange the new maximum with the   */
164  {                        /* element at the end of the tree         */
165    temp_a   = a[i];
166    temp_idx = idx[i];
167    a[i]     = a[0];
168    idx[i]   = idx[0];
169    a[0]     = temp_a;
170    idx[0]     = temp_idx;
171    PGAAdjustHeap(ctx, a, idx, 0, i, j, item, item_idx);
172  }
173
174    PGADebugExited("PGADblHeapSort");
175}
176
177
178
179
180/*I****************************************************************************
181   PGAIntHeapSort - Uses a heapsort algorithm to sort from largest to smallest
182   element.  An integer array, intialized with the original indices of the
183   elements of array a is sorted also so that the original locations are known
184
185   Category: Sorting
186
187   Inputs:
188       ctx      - context variable
189       a        - array of (int) values to be sorted
190       idx      - array of integer indices corresponding to the array
191                  a being sorted
192       n        - size of the arrays a and idx
193
194   Output:
195       The sorted arrays a and idx
196
197   Example:
198      The following code sorts the population by fitness
199
200      PGAContext *ctx;
201      int i,j,n,idx[LARGE],a[LARGE];
202      :
203      n = PGAGetPopsize(ctx);
204      for(i=0;i<n;i++) {
205        a[i]   = (int) PGAGetEvaluation(ctx,p,PGA_OLDPOP);
206        idx[i] = i;
207      }
208      PGAIntHeapSort ( ctx, a, idx, n);
209
210****************************************************************************I*/
211void PGAIntHeapSort ( PGAContext *ctx, int *a, int *idx, int n )
212{
213  int i;                   /* index of for loops                      */
214  int temp_a;
215  int temp_idx;
216  int j, item_idx;
217  double item;
218
219    PGADebugEntered("PGAIntHeapSort");
220
221  /*  Create a heap from our elements.  */
222  for (i=(n-2)/2; i>=0; i--)
223    PGAAdjustHeap(ctx, a, idx, i, n, j, item, item_idx);
224
225  for ( i=n-1; i>=1; i--)  /* interchange the new maximum with the   */
226  {                        /* element at the end of the tree         */
227    temp_a   = a[i];
228    temp_idx = idx[i];
229    a[i]     = a[0];
230    idx[i]   = idx[0];
231    a[0]     = temp_a;
232    idx[0]     = temp_idx;
233    PGAAdjustHeap(ctx, a, idx, 0, i, j, item, item_idx);
234  }
235
236    PGADebugExited("PGAIntHeapSort");
237}
238
239
Note: See TracBrowser for help on using the repository browser.