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: %6d\n", poll(&heapS) );
print_heap(heapS);

printf("peek:    %6d\n", peek(heapS) );
print_heap(heapS);

printf("add:     %6d\n", 17);
add(&heapS, 17);
print_heap(heapS);

printf("removed: %6d\n", poll(&heapS) );
print_heap(heapS);

printf("removed: %6d\n", 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:     %6d\n", 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)