src/common/maxheap.c

#ifndef lint
static const char RCSid[] = "$Id$";
#endif
#include <stdio.h>
#include <stdlib.h>

#include "maxheap.h"


static  int     resize_heap(maxHeap* hp,int sz)
{
        int i;

        if (sz == hp->cap)
                return 1;
        hp->heap = (heapElem*) realloc(hp->heap,sz*sizeof(heapElem));
        if (!hp->heap) 
                return 0;
        for(i=hp->size;i<sz;i++) {
                hp->heap[i].entity = NULL;
                hp->heap[i].key = -HUGE;
        }
        hp->cap = sz;
        if (sz < hp->size) {
                hp->size = sz;
                hp->state = HP_INVALID;
        }
        if (sz == 0) {
                hp->heap = NULL;
                hp->state = HP_BUILD;
        }
        return 1;
}

int             mheap_init(maxHeap* hp)
{
        hp->size = 0;
        hp->cap  = 0;
        hp->heap = NULL;
        hp->state = HP_BUILD;
        return resize_heap(hp,HP_STARTCAP);
}

void    mheap_free(maxHeap* hp)
{
        resize_heap(hp,0);
        free(hp);
}

maxHeap*        mheap_create()
{
        maxHeap* res = (maxHeap*) calloc(1,sizeof(maxHeap));
        if (!res) {
                fprintf(stderr,"Error allocating heap struct\n");
                return NULL;
        }
        if (!mheap_init(res))
                return NULL;
        return res;
}
                

static  void    swap_elem(heapElem* e1,heapElem* e2)
{
        heapElem e;

        e = *e1;
        *e1 = *e2;
        *e2 = e;
}

static  void    heapify(maxHeap* hp,int i)
{
        int     l,r,m;

        l = mh_left(i);
        r = mh_right(i);
        if ((l < hp->size) && (hp->heap[l].key > hp->heap[i].key)) 
                m = l;
        else
                m = i;
        if ((r < hp->size) && (hp->heap[m].key < hp->heap[r].key))
                m = r;
        if (m != i) {
                swap_elem(&(hp->heap[m]),&(hp->heap[i]));
                heapify(hp,m);
        }
}

void    mheap_build(maxHeap* hp)
{
        int i;

        for(i=((int) hp->size/2)-1;i>=0;i--) 
                heapify(hp,i);
        hp->state = HP_BUILD;
}

void    mheap_sort(maxHeap* hp)
{
        int i,sz;

        if (hp->state == HP_SORTED) 
                return;
        if (hp->state != HP_BUILD)
                mheap_build(hp);
        sz = hp->size;
        for(i=(hp->size-1);i>0;i--) {
                swap_elem(&(hp->heap[0]),&(hp->heap[i]));
                hp->size--;
                heapify(hp,0);
        }
        hp->size = sz;
        hp->state = HP_SORTED;
}
                
                
heapElem        mheap_remove_max(maxHeap* hp)
{
        heapElem res;
        if (hp->size < 1) {
                res.key = -HUGE;
                res.entity = NULL;
                return res;
        }       
        res = hp->heap[0];
        hp->heap[0] = hp->heap[hp->size - 1];
        hp->size--;
        heapify(hp,0);
        return res;
}

static  int     inc_key(maxHeap* hp,int i,g3Float k)
{
        if (k < hp->heap[i].key) {
                fprintf(stderr,"New key error in inc_key(mheap)\n");
                hp->state = HP_INVALID;
                return 0;
        }
        hp->heap[i].key = k;
        while((i > 0) && (hp->heap[mh_parent(i)].key < hp->heap[i].key)) {
                swap_elem(&(hp->heap[mh_parent(i)]),&(hp->heap[i]));
                i = mh_parent(i);
        }
        return 1;
}

int             mheap_insert(maxHeap* hp,g3Float key,void* entity)
{
        if (hp->size == hp->cap) {
                if (!resize_heap(hp,hp->cap*2)) {
                        hp->state = HP_INVALID;
                        return 0;
                }
        }
        hp->heap[hp->size].entity = entity;
        hp->heap[hp->size].key = -HUGE;
        hp->size++;
        return inc_key(hp,(hp->size - 1),key);
}


#ifdef  TEST_MHEAP
#include "timeutil.h"
                
int             main(int argc,char** argv)
{
        g3Float* k;
        int i,n;
        maxHeap* hp;
        heapElem e;
        double t;
        hp = mheap_create();

        if (argc > 1)
                n = atoi(argv[1]);
        else
                n = 10;
        
        t = get_time();
        for(i=0;i<n;i++) {
                k = (g3Float*) malloc(sizeof(g3Float));
                *k = 10.0*rand()/RAND_MAX;
                if (!mheap_insert(hp,*k,k)) {
                        fprintf(stderr,"Error inserting\n");
                        return EXIT_FAILURE;
                }
        }
        t = get_time() - t;
        fprintf(stderr,"insert: %d %f\n",n,t);
        t = get_time();
        mheap_sort(hp);
        t = get_time() - t;
        fprintf(stderr,"sort: %d %f\n",n,t);
        for(i=0;i<n;i++) 
                printf("%d %f \n",i,hp->heap[i].key);
        printf("-------------\n");
        t = get_time();
        mheap_build(hp);
        t = get_time() - t;
        fprintf(stderr,"build: %d %f\n",n,t);
        for(i=0;i<n;i++) {
                e = mheap_remove_max(hp);
                printf("%d %f \n",hp->size,e.key);
                if ((i < (n-1)) && (e.key < mheap_get_max(hp).key)) {
                        fprintf(stderr,"oooops: not sorted\n");
                }
        }
        return EXIT_SUCCESS;
}

#endif
Revision:	2.2
Committed:	Tue Aug 18 15:02:53 2015 UTC (8 years, 8 months ago) by greg
Content type:	text/plain
Branch:	MAIN
CVS Tags:	rad5R0, rad5R1
Changes since 2.1:	+3 -0 lines
Log Message:	Added RCCS id's to new source files (forgotten during initial check-in)
#	User	Rev	Content
1	greg	2.2	#ifndef lint
2			static const char RCSid[] = "$Id$";
3			#endif
4	greg	2.1	#include <stdio.h>
5			#include <stdlib.h>
6
7			#include "maxheap.h"
8
9
10			static int resize_heap(maxHeap* hp,int sz)
11			{
12			int i;
13
14			if (sz == hp->cap)
15			return 1;
16			hp->heap = (heapElem) realloc(hp->heap,szsizeof(heapElem));
17			if (!hp->heap)
18			return 0;
19			for(i=hp->size;i<sz;i++) {
20			hp->heap[i].entity = NULL;
21			hp->heap[i].key = -HUGE;
22			}
23			hp->cap = sz;
24			if (sz < hp->size) {
25			hp->size = sz;
26			hp->state = HP_INVALID;
27			}
28			if (sz == 0) {
29			hp->heap = NULL;
30			hp->state = HP_BUILD;
31			}
32			return 1;
33			}
34
35			int mheap_init(maxHeap* hp)
36			{
37			hp->size = 0;
38			hp->cap = 0;
39			hp->heap = NULL;
40			hp->state = HP_BUILD;
41			return resize_heap(hp,HP_STARTCAP);
42			}
43
44			void mheap_free(maxHeap* hp)
45			{
46			resize_heap(hp,0);
47			free(hp);
48			}
49
50			maxHeap* mheap_create()
51			{
52			maxHeap* res = (maxHeap*) calloc(1,sizeof(maxHeap));
53			if (!res) {
54			fprintf(stderr,"Error allocating heap struct\n");
55			return NULL;
56			}
57			if (!mheap_init(res))
58			return NULL;
59			return res;
60			}
61
62
63			static void swap_elem(heapElem* e1,heapElem* e2)
64			{
65			heapElem e;
66
67			e = *e1;
68			e1 = e2;
69			*e2 = e;
70			}
71
72			static void heapify(maxHeap* hp,int i)
73			{
74			int l,r,m;
75
76			l = mh_left(i);
77			r = mh_right(i);
78			if ((l < hp->size) && (hp->heap[l].key > hp->heap[i].key))
79			m = l;
80			else
81			m = i;
82			if ((r < hp->size) && (hp->heap[m].key < hp->heap[r].key))
83			m = r;
84			if (m != i) {
85			swap_elem(&(hp->heap[m]),&(hp->heap[i]));
86			heapify(hp,m);
87			}
88			}
89
90			void mheap_build(maxHeap* hp)
91			{
92			int i;
93
94			for(i=((int) hp->size/2)-1;i>=0;i--)
95			heapify(hp,i);
96			hp->state = HP_BUILD;
97			}
98
99			void mheap_sort(maxHeap* hp)
100			{
101			int i,sz;
102
103			if (hp->state == HP_SORTED)
104			return;
105			if (hp->state != HP_BUILD)
106			mheap_build(hp);
107			sz = hp->size;
108			for(i=(hp->size-1);i>0;i--) {
109			swap_elem(&(hp->heap[0]),&(hp->heap[i]));
110			hp->size--;
111			heapify(hp,0);
112			}
113			hp->size = sz;
114			hp->state = HP_SORTED;
115			}
116
117
118			heapElem mheap_remove_max(maxHeap* hp)
119			{
120			heapElem res;
121			if (hp->size < 1) {
122			res.key = -HUGE;
123			res.entity = NULL;
124			return res;
125			}
126			res = hp->heap[0];
127			hp->heap[0] = hp->heap[hp->size - 1];
128			hp->size--;
129			heapify(hp,0);
130			return res;
131			}
132
133			static int inc_key(maxHeap* hp,int i,g3Float k)
134			{
135			if (k < hp->heap[i].key) {
136			fprintf(stderr,"New key error in inc_key(mheap)\n");
137			hp->state = HP_INVALID;
138			return 0;
139			}
140			hp->heap[i].key = k;
141			while((i > 0) && (hp->heap[mh_parent(i)].key < hp->heap[i].key)) {
142			swap_elem(&(hp->heap[mh_parent(i)]),&(hp->heap[i]));
143			i = mh_parent(i);
144			}
145			return 1;
146			}
147
148			int mheap_insert(maxHeap* hp,g3Float key,void* entity)
149			{
150			if (hp->size == hp->cap) {
151			if (!resize_heap(hp,hp->cap*2)) {
152			hp->state = HP_INVALID;
153			return 0;
154			}
155			}
156			hp->heap[hp->size].entity = entity;
157			hp->heap[hp->size].key = -HUGE;
158			hp->size++;
159			return inc_key(hp,(hp->size - 1),key);
160			}
161
162
163			#ifdef TEST_MHEAP
164			#include "timeutil.h"
165
166			int main(int argc,char** argv)
167			{
168			g3Float* k;
169			int i,n;
170			maxHeap* hp;
171			heapElem e;
172			double t;
173			hp = mheap_create();
174
175			if (argc > 1)
176			n = atoi(argv[1]);
177			else
178			n = 10;
179
180			t = get_time();
181			for(i=0;i<n;i++) {
182			k = (g3Float*) malloc(sizeof(g3Float));
183			k = 10.0rand()/RAND_MAX;
184			if (!mheap_insert(hp,*k,k)) {
185			fprintf(stderr,"Error inserting\n");
186			return EXIT_FAILURE;
187			}
188			}
189			t = get_time() - t;
190			fprintf(stderr,"insert: %d %f\n",n,t);
191			t = get_time();
192			mheap_sort(hp);
193			t = get_time() - t;
194			fprintf(stderr,"sort: %d %f\n",n,t);
195			for(i=0;i<n;i++)
196			printf("%d %f \n",i,hp->heap[i].key);
197			printf("-------------\n");
198			t = get_time();
199			mheap_build(hp);
200			t = get_time() - t;
201			fprintf(stderr,"build: %d %f\n",n,t);
202			for(i=0;i<n;i++) {
203			e = mheap_remove_max(hp);
204			printf("%d %f \n",hp->size,e.key);
205			if ((i < (n-1)) && (e.key < mheap_get_max(hp).key)) {
206			fprintf(stderr,"oooops: not sorted\n");
207			}
208			}
209			return EXIT_SUCCESS;
210			}
211
212			#endif