Data structure and algorithm heap
Can someone help me with this?
heap.h
#ifndef HEAP_H
#define HEAP_Hstruct 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)
