Data structure and algorithm heap

 

Can someone help me with this?

​​​​​​​Points: 100 Topics: MaxHeap, array resizing For this assignment you will: - represent a heap using the struct defined at theFormat of test files: where the first 2 lines specify an array of ( mathrm{N} ) integers and the next 2 lines specify ( 1. Write your name at the top of each .c file you submit and use good coding style: indentation, variable names. Points will

heap.h
#ifndef HEAP_H
#define HEAP_H

struct heap_struct {
int* items;
int N;  // current size
int capacity; // array capacity
};

// max-heap operations

struct heap_struct make_heap_empty(int cap);

// assumes arr was dynamically allocated.
struct heap_struct make_heap(int N, int * arr); // makes a max-heap from arr. Asssumes both size and capacity are N.

// Will free the heap array.
void destroy(struct heap_struct * heapP);

void print_heap(struct heap_struct heapS);

void sink_down(int i, int N, int * arr);
void swim_up(int idx, int * arr);

int peek(struct heap_struct heapS);
int poll(struct heap_struct * heapP);
void add(struct heap_struct * heapP, int new_item);// will resize the heap if needed

#endif /* HEAP_H */


heap_calls.c

/* compile:
gcc -g heap_calls.c heap.c
run:
./a.out

Valgrind:
valgrind --leak-check=full ./a.out
*
*/

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#include "heap.h"  

int main()   {
int N,k,i;
char fname[501];
int debug = 0;
struct heap_struct heapS;
printf("This program will call the heap functions.n ");   
  

N = 3;
int *arr = (int*) calloc(N, sizeof(int) );
arr[0] = 10;
arr[1] = 20;
arr[2] = 43;

heapS = make_heap(N, arr);         
print_heap(heapS);

printf("removed: %6dn", poll(&heapS) );
print_heap(heapS);

printf("peek:    %6dn", peek(heapS) );
print_heap(heapS);

printf("add:     %6dn", 17);
add(&heapS, 17);
print_heap(heapS);

printf("removed: %6dn", poll(&heapS) );
print_heap(heapS);

printf("removed: %6dn", poll(&heapS) );
print_heap(heapS);
  
destroy(&heapS);   
printf("After call to destroy (1)n");
print_heap(heapS);
  
heapS = make_heap_empty(11);
printf("Created empty heap: n");
print_heap(heapS);

printf("add:     %6dn", 204);
add(&heapS, 204);
print_heap(heapS);

destroy(&heapS);   
printf("After call to destroy(2)n");
print_heap(heapS);

destroy(&heapS);   
printf("After call to destroy(3)n");
print_heap(heapS);

return 0;
}

heap_calls.c heap.c
gcc -g heap_calls.c heap.c
valgrind --leak-check=full ./a.out
==185== Memcheck, a memory error detector
==185== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==185== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==185== Command: ./a.out
==185==
This program will call the heap functions.
in function make_heap, in DEBUG MODE, printing array BEFORE it gets turned into a heap :
Heap:  size: 3, capacity : 3
indexes:           0,      1,      2,
values:           10,     20,     43,

in function make_heap, in DEBUG MODE, printing array after sink_down at index 0.
Heap:  size: 3, capacity : 3
indexes:           0,      1,      2,
values:           43,     20,     10,

Heap:  size: 3, capacity : 3
indexes:           0,      1,      2,
values:           43,     20,     10,

removed:     43
Heap:  size: 2, capacity : 3
indexes:           0,      1,
values:           20,     10,

peek:        20
Heap:  size: 2, capacity : 3
indexes:           0,      1,
values:           20,     10,

add:         17
Heap:  size: 3, capacity : 3
indexes:           0,      1,      2,
values:           20,     10,     17,

removed:     20
Heap:  size: 2, capacity : 3
indexes:           0,      1,
values:           17,     10,

removed:     17
Heap:  size: 1, capacity : 3
indexes:           0,
values:           10,

After call to destroy (1)
Heap:  size: 0, capacity : 0
indexes:
values:

Created empty heap:
Heap:  size: 0, capacity : 11
indexes:
values:

add:        204
Heap:  size: 1, capacity : 11
indexes:           0,
values:          204,

After call to destroy(2)
Heap:  size: 0, capacity : 0
indexes:
values:

After call to destroy(3)
Heap:  size: 0, capacity : 0
indexes:
values:

==185==
==185== HEAP SUMMARY:
==185==     in use at exit: 0 bytes in 0 blocks
==185==   total heap usage: 3 allocs, 3 frees, 1,080 bytes allocated
==185==
==185== All heap blocks were freed -- no leaks are possible
==185==
==185== For lists of detected and suppressed errors, rerun with: -s
==185== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

heap.c
​​​​​​​#include <stdlib.h>
#include <stdio.h>

#include "heap.h"  

#define DEBUG 1

/*
struct heap_struct make_heap_empty(int cap){
}

struct heap_struct make_heap(int N, int * arr){
}

void destroy(struct heap_struct * heapP){
}

void print_heap(struct heap_struct heapS){
}

void swim_up(int idx, int * arr){
}

void sink_down(int i, int N, int * arr){
}

void add(struct heap_struct * heapP, int new_item){
}

int peek(struct heap_struct heapS){
}

int poll(struct heap_struct * heapP){
}

*/

all_opt.txt

5
10 40 20 50 90
6
13 * 82 p P *

empty.txt

2
10 40
10
* * * * 12 * 85 39 * *

resize.txt

2
10 40
9
5 -6 85 1 2 3 4 5 6 

// run all_opt.txt example

gcc -g run_test.c heap.c
valgrind --leak-check=full ./a.out
==170== Memcheck, a memory error detector
==170== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==170== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==170== Command: ./a.out
==170==
This program will create a max-heap and perform operations on it based on data from a file.

Enter the filename: all_ops.txt
in function make_heap, in DEBUG MODE, printing array BEFORE it gets turned into a heap :
Heap:  size: 5, capacity : 5
indexes:           0,      1,      2,      3,      4,
values:           10,     40,     20,     50,     90,

in function make_heap, in DEBUG MODE, printing array after sink_down at index 1.
Heap:  size: 5, capacity : 5
indexes:           0,      1,      2,      3,      4,
values:           10,     90,     20,     50,     40,

in function make_heap, in DEBUG MODE, printing array after sink_down at index 0.
Heap:  size: 5, capacity : 5
indexes:           0,      1,      2,      3,      4,
values:           90,     50,     20,     10,     40,

Heap:  size: 5, capacity : 5
indexes:           0,      1,      2,      3,      4,
values:           90,     50,     20,     10,     40,

Operation number 1, string: 13
add:          13

resizing
Heap:  size: 6, capacity : 10
indexes:           0,      1,      2,      3,      4,      5,
values:           90,     50,     20,     10,     40,     13,

Operation number 2, string: *
removed:     90
Heap:  size: 5, capacity : 10
indexes:           0,      1,      2,      3,      4,
values:           50,     40,     20,     10,     13,

Operation number 3, string: 82
add:          82
Heap:  size: 6, capacity : 10
indexes:           0,      1,      2,      3,      4,      5,
values:           82,     40,     50,     10,     13,     20,

Operation number 4, string: p
peek:        82
Heap:  size: 6, capacity : 10
indexes:           0,      1,      2,      3,      4,      5,
values:           82,     40,     50,     10,     13,     20,

Operation number 5, string: P
peek:        82
Heap:  size: 6, capacity : 10
indexes:           0,      1,      2,      3,      4,      5,
values:           82,     40,     50,     10,     13,     20,

Operation number 6, string: *
removed:     82
Heap:  size: 5, capacity : 10
indexes:           0,      1,      2,      3,      4,
values:           50,     40,     20,     10,     13,

==170==
==170== HEAP SUMMARY:
==170==     in use at exit: 0 bytes in 0 blocks
==170==   total heap usage: 6 allocs, 6 frees, 6,676 bytes allocated
==170==
==170== All heap blocks were freed -- no leaks are possible
==170==
==170== For lists of detected and suppressed errors, rerun with: -s
==170== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Place your order
(550 words)

Approximate price: $22

Calculate the price of your order

550 words
We'll send you the first draft for approval by September 11, 2018 at 10:52 AM
Total price:
$26
The price is based on these factors:
Academic level
Number of pages
Urgency
Basic features
  • Free title page and bibliography
  • Unlimited revisions
  • Plagiarism-free guarantee
  • Money-back guarantee
  • 24/7 support
On-demand options
  • Writer’s samples
  • Part-by-part delivery
  • Overnight delivery
  • Copies of used sources
  • Expert Proofreading
Paper format
  • 275 words per page
  • 12 pt Arial/Times New Roman
  • Double line spacing
  • Any citation style (APA, MLA, Chicago/Turabian, Harvard)

Our guarantees

Delivering a high-quality product at a reasonable price is not enough anymore.
That’s why we have developed 5 beneficial guarantees that will make your experience with our service enjoyable, easy, and safe.

Money-back guarantee

You have to be 100% sure of the quality of your product to give a money-back guarantee. This describes us perfectly. Make sure that this guarantee is totally transparent.

Read more

Zero-plagiarism guarantee

Each paper is composed from scratch, according to your instructions. It is then checked by our plagiarism-detection software. There is no gap where plagiarism could squeeze in.

Read more

Free-revision policy

Thanks to our free revisions, there is no way for you to be unsatisfied. We will work on your paper until you are completely happy with the result.

Read more

Privacy policy

Your email is safe, as we store it according to international data protection rules. Your bank details are secure, as we use only reliable payment systems.

Read more

Fair-cooperation guarantee

By sending us your money, you buy the service we provide. Check out our terms and conditions if you prefer business talks to be laid out in official language.

Read more