src/common/maxheap.c

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