	[x] Posted via EE Mobile
	Search, ask, and monitor your questions on the go with EE Mobile. Visit Experts Exchange from your mobile device and never be out of touch again.

Question

	[x] Attachment Details

[x]

The Solution Rating System

With so many solutions, how can you tell which solutions are most likely to help you and which ones are not? To provide you with a tool to use, we rate our solutions based on various elements that most accurately determine if a solution is a quality solution. To explain what factors affect the solution rating, here are the elements we take into consideration when formulating our solution rating.

The Grade of the Solution
The Zone Rank of the Expert Providing the Solution
The Number of Author and Expert Comments
The Number of Experts Contributing
The Feedback of the Community

Your Input Matters
Because of the way the system is set up, the most important variable in this equation is you. As a member of Experts Exchange, you are able to cast your vote on the quality of the solutions in regard to how complete, accurate, helpful and easy to understand each solution is. When you provide your feedback, each rating is adjusted accordingly. So, if you see a solution that has a poor rating that you think is a good solution, let us know by rating it. As you do, the rating will be adjusted and will become more accurate for other members of our site.

If you have any suggestions that you would like to make for our rating system, please ask a question in the Suggestions Zone of Community Support.

Thank you!

7.8

an assignment using heaps

Asked by mikeregas in C Programming Language

I have one last assignment for the semester using heaps. I was wondering if anyone could explain how they are used and what is the best way to implement it in this assignment. I have the sample heap code that he gave us in class and I also will attach the actual assignment so that you can understand it better.

View the Solution FREE for 30 Days

         
           
             1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:
236:
237:
238:
239:

           
           
             /*George Regas
  COP 3205
  Assignment 5
  12/05/08
*/
 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
struct heap
{
    int* store;
    int size; // Number of values in the heap
    int capacity; // Maximum number of values before we
                  // expand the heap
};
 
void insert(struct heap* h, int value); // done
int findmin(struct heap* h); // done
int deletemin(struct heap* h); // done
 
struct heap* new_heap(int initial_capacity); //done
struct heap* heapify(int array[], int num_elements); //done
 
void percolate_up(struct heap* h, int position); //done
void percolate_down(struct heap* h, int position); //done
void expand_heap(struct heap* h); //done
int is_heap_empty(struct heap* h); // done
 
int main(void)
{
    int i; // Loop index
    struct heap* h; // The heap that we're manipulating
    int choice; // The user's menu choice 
    int data; // The data element to add to the heap
    int num_values; // The number of random values to add to the heap
    
    // Set up the heap and seed the RNG
    h = new_heap(16);
    srand(time(NULL));
        
    do
    {
        printf("Here are your options:\n");
        printf("1. Add a value to the heap\n");
        printf("2. Find the minimum value in the heap\n");
        printf("3. Delete the minimum value in the heap\n");
        printf("4. Add a bunch of random data to the heap\n");
        printf("5. Purge the heap, printing its contents in sorted order\n");
        printf("0. Quit\n");
        scanf("%d", &choice);
        
        if(choice == 1)
        {
            printf("What do you want to add to the heap?\n");
            scanf("%d", &data);
            insert(h, data);
            printf("Added %d to the heap\n", data);
        }
        else if(choice == 2)
        {
            if(!is_heap_empty(h))
                printf("The smallest value in the heap is %d\n", findmin(h));
            else
                printf("The heap is empty!\n");
        }
        else if(choice == 3)
        {
            if(!is_heap_empty(h))
                printf("Deleted %d from the heap\n", deletemin(h));
            else
                printf("The heap is empty!\n");
        }
        else if(choice == 4)
        {
            printf("How many numbers do you want to add to the heap?\n");
            scanf("%d", &num_values);
            
            for(i = 0; i < num_values; i++)
                insert(h, (rand() << 15) + rand());
        }
        else if(choice == 5)
        {
            printf("Purging heap:\n");
            i = 0;
            while(!is_heap_empty(h))
            {
                printf("%10d ", deletemin(h));   
                i++;
                if(i % 7 == 0)
                    printf("\n");
            }
            printf("\n");
        }
    }while(choice != 0);
    
    system("PAUSE");
    return 0;   
}
 
struct heap* heapify(int array[], int num_elements)
{
    struct heap* h;
    int i;
    
    h = new_heap((num_elements + 1) * 2);
    
    for(i = 0; i < num_elements; i++)
    {
        h->store[i+1] = array[i];   
    }
    h->size = num_elements;
    
    for(i = h->size / 2; i >= 1; i--)
        percolate_down(h, i);
        
    return h;
}
 
struct heap* new_heap(int initial_capacity)
{
    struct heap* h;
    
    h = malloc(sizeof(struct heap));
    h->store = calloc(initial_capacity, sizeof(int));
    h->size = 0;
    h->capacity = initial_capacity;   
    
    return h;
}
 
void expand_heap(struct heap* h)
{
    int* newstore;
    int i;
    
    newstore = calloc(h->capacity * 2, sizeof(int));
    
    for(i = 1; i <= h->size; i++)
    {
        newstore[i] = h->store[i];   
    }
    free(h->store);
    h->store = newstore;
    h->capacity *= 2;
}
 
void percolate_down(struct heap* h, int position)
{
    int temp;
    if(position * 2 > h->size)
        return;
        
    if(position * 2 == h->size)
    {
        if(h->store[position*2] >= h->store[position])
            return;
        else
        {
            temp = h->store[position];   
            h->store[position] = h->store[position*2];
            h->store[position*2] = temp;
            return;
        }
    }
    
    if(h->store[position*2] >= h->store[position] 
            && h->store[position*2 + 1] >= h->store[position])
        return;
    
    // Percolate to the left
    if(h->store[position*2] <= h->store[position*2 + 1])
    {
        temp = h->store[position];
        h->store[position] = h->store[position*2];
        h->store[position*2] = temp;
        percolate_down(h, position * 2);
        return;
    }
    
    // Percolate to the right
    temp = h->store[position];
    h->store[position] = h->store[position*2 + 1];
    h->store[position*2 + 1] = temp;
    percolate_down(h, position * 2 + 1);
 
}
 
void percolate_up(struct heap* h, int position)
{
    int temp;
    
    if(position == 1)
        return;
    if(h->store[position/2] <= h->store[position])
        return; 
    
    temp = h->store[position];
    h->store[position] = h->store[position/2];
    h->store[position/2] = temp;
    
    percolate_up(h, position/2);
}
 
int deletemin(struct heap* h)
{
    int rval = h->store[1];
    h->store[1] = h->store[h->size];
    h->size--;
    
    percolate_down(h, 1);
    
    return rval;
}
 
void insert(struct heap* h, int value)
{
    h->size++;
    if(h->size >= h->capacity)
        expand_heap(h);
    
    h->store[h->size] = value;
    percolate_up(h, h->size);
}
 
int is_heap_empty(struct heap* h)
{
    if(h->size == 0)   
        return 1;
    else
        return 0;
}
 
 
int findmin(struct heap* h)
{
    return h->store[1];   
}

           
         

Attachments:

Assignment5.doc (28 KB) (File Type Details)

This is the assignment.

	Title
1	Basic Questions about GDI+ and VB …
2	Please check tree code.
3	Linking assembler and c code with vis…
4	Translate Excel's macro to embedded…
5	Multithread

an assignment using heaps

Asked by mikeregas in C Programming Language

About this solution