{"id":99312,"date":"2022-10-13T09:53:47","date_gmt":"2022-10-13T09:53:47","guid":{"rendered":"https:\/\/assignmenttutors.net\/blog\/data-structure-and-algorithm-heap\/"},"modified":"2022-10-13T09:53:47","modified_gmt":"2022-10-13T09:53:47","slug":"data-structure-and-algorithm-heap","status":"publish","type":"post","link":"https:\/\/assignmenttutors.net\/blog\/data-structure-and-algorithm-heap\/","title":{"rendered":"Data structure and algorithm heap"},"content":{"rendered":"
\n

\u00a0<\/p>\n

Can someone help me with this?<\/p>\n

\u200b\u200b\u200b\u200b\u200b\u200b\u200b\"Points:\"Format\"1.<\/p>\n

heap.h#ifndef HEAP_H#define\tHEAP_H
struct heap_struct {int* items;int N; \u00a0\/\/ current sizeint capacity; \/\/ array capacity};<\/p>
\/\/ max-heap operations<\/p>
struct heap_struct make_heap_empty(int cap);<\/p>
\/\/ 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.<\/p>
\/\/ Will free the heap array.void destroy(struct heap_struct * heapP);<\/p>
void print_heap(struct heap_struct heapS);<\/p>
void sink_down(int i, int N, int * arr);void swim_up(int idx, int * arr);<\/p>
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<\/p>
#endif\t\/* HEAP_H *\/<\/p><\/code><\/pre>\n
heap_calls.c
\/* compile: gcc -g heap_calls.c heap.crun:.\/a.out <\/p>
Valgrind:valgrind --leak-check=full .\/a.out * *\/<\/p>
#include <stdlib.h>#include <stdio.h>#include <string.h><\/p>
#include \"heap.h\" \u00a0<\/p>
int main() \u00a0\u00a0{int N,k,i;char fname[501];int debug = 0;struct heap_struct heapS;printf(\"This program will call the heap functions.n \"); \u00a0\u00a0\u00a0\u00a0<\/p>
N = 3;int *arr = (int*) calloc(N, sizeof(int) );arr[0] = 10;arr[1] = 20;arr[2] = 43;<\/p>
heapS = make_heap(N, arr); \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0print_heap(heapS);<\/p>
printf(\"removed: %6dn\", poll(&heapS) );\tprint_heap(heapS);<\/p>
printf(\"peek: \u00a0\u00a0\u00a0%6dn\", peek(heapS) );print_heap(heapS);<\/p>
printf(\"add: \u00a0\u00a0\u00a0\u00a0%6dn\", 17);\tadd(&heapS, 17);print_heap(heapS);<\/p>
printf(\"removed: %6dn\", poll(&heapS) );\tprint_heap(heapS);<\/p>
printf(\"removed: %6dn\", poll(&heapS) );\tprint_heap(heapS);\u00a0\u00a0destroy(&heapS); \u00a0\u00a0printf(\"After call to destroy (1)n\");print_heap(heapS);\u00a0\u00a0heapS = make_heap_empty(11);printf(\"Created empty heap: n\");print_heap(heapS);<\/p>
printf(\"add: \u00a0\u00a0\u00a0\u00a0%6dn\", 204);\tadd(&heapS, 204);print_heap(heapS);\t<\/p>
destroy(&heapS); \u00a0\u00a0printf(\"After call to destroy(2)n\");print_heap(heapS);<\/p>
destroy(&heapS); \u00a0\u00a0printf(\"After call to destroy(3)n\");print_heap(heapS);<\/p>
return 0;}<\/p><\/code><\/pre>\n
heap_calls.c heap.cgcc -g heap_calls.c heap.cvalgrind --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: \u00a0size: 3, capacity : 3indexes: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a00, \u00a0\u00a0\u00a0\u00a0\u00a01, \u00a0\u00a0\u00a0\u00a0\u00a02,values: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a010, \u00a0\u00a0\u00a0\u00a020, \u00a0\u00a0\u00a0\u00a043,
in function make_heap, in DEBUG MODE, printing array after sink_down at index 0.Heap: \u00a0size: 3, capacity : 3indexes: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a00, \u00a0\u00a0\u00a0\u00a0\u00a01, \u00a0\u00a0\u00a0\u00a0\u00a02,values: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a043, \u00a0\u00a0\u00a0\u00a020, \u00a0\u00a0\u00a0\u00a010,<\/p>
Heap: \u00a0size: 3, capacity : 3indexes: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a00, \u00a0\u00a0\u00a0\u00a0\u00a01, \u00a0\u00a0\u00a0\u00a0\u00a02,values: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a043, \u00a0\u00a0\u00a0\u00a020, \u00a0\u00a0\u00a0\u00a010,<\/p>
removed: \u00a0\u00a0\u00a0\u00a043Heap: \u00a0size: 2, capacity : 3indexes: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a00, \u00a0\u00a0\u00a0\u00a0\u00a01,values: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a020, \u00a0\u00a0\u00a0\u00a010,<\/p>
peek: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a020Heap: \u00a0size: 2, capacity : 3indexes: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a00, \u00a0\u00a0\u00a0\u00a0\u00a01,values: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a020, \u00a0\u00a0\u00a0\u00a010,<\/p>
add: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a017Heap: \u00a0size: 3, capacity : 3indexes: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a00, \u00a0\u00a0\u00a0\u00a0\u00a01, \u00a0\u00a0\u00a0\u00a0\u00a02,values: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a020, \u00a0\u00a0\u00a0\u00a010, \u00a0\u00a0\u00a0\u00a017,<\/p>
removed: \u00a0\u00a0\u00a0\u00a020Heap: \u00a0size: 2, capacity : 3indexes: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a00, \u00a0\u00a0\u00a0\u00a0\u00a01,values: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a017, \u00a0\u00a0\u00a0\u00a010,<\/p>
removed: \u00a0\u00a0\u00a0\u00a017Heap: \u00a0size: 1, capacity : 3indexes: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a00,values: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a010,<\/p>
After call to destroy (1)Heap: \u00a0size: 0, capacity : 0indexes:values:<\/p>
Created empty heap:Heap: \u00a0size: 0, capacity : 11indexes:values:<\/p>
add: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0204Heap: \u00a0size: 1, capacity : 11indexes: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a00,values: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0204,<\/p>
After call to destroy(2)Heap: \u00a0size: 0, capacity : 0indexes:values:<\/p>
After call to destroy(3)Heap: \u00a0size: 0, capacity : 0indexes:values:<\/p>
==185====185== HEAP SUMMARY:==185== \u00a0\u00a0\u00a0\u00a0in use at exit: 0 bytes in 0 blocks==185== \u00a0\u00a0total 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)<\/p><\/code><\/pre>\n
heap.c\u200b\u200b\u200b\u200b\u200b\u200b\u200b#include <stdlib.h>#include <stdio.h>
#include \"heap.h\" \u00a0<\/p>
#define DEBUG 1<\/p>
\/*struct heap_struct make_heap_empty(int cap){}<\/p>
struct heap_struct make_heap(int N, int * arr){}<\/p>
void destroy(struct heap_struct * heapP){}<\/p>
void print_heap(struct heap_struct heapS){}<\/p>
void swim_up(int idx, int * arr){}<\/p>
void sink_down(int i, int N, int * arr){}<\/p>
void add(struct heap_struct * heapP, int new_item){}<\/p>
int peek(struct heap_struct heapS){}<\/p>
int poll(struct heap_struct * heapP){}<\/p>
*\/<\/p><\/code><\/pre>\n
all_opt.txt<\/p>\n
510 40 20 50 90613 * 82 p P *<\/code><\/pre>\n
empty.txt<\/p>\n
210 4010* * * * 12 * 85 39 * *<\/code><\/pre>\n
resize.txt<\/p>\n
210 4095 -6 85 1 2 3 4 5 6\u00a0<\/code><\/pre>\n
\/\/ run all_opt.txt example<\/p>\n
gcc -g run_test.c heap.cvalgrind --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.txtin function make_heap, in DEBUG MODE, printing array BEFORE it gets turned into a heap :Heap: \u00a0size: 5, capacity : 5indexes: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a00, \u00a0\u00a0\u00a0\u00a0\u00a01, \u00a0\u00a0\u00a0\u00a0\u00a02, \u00a0\u00a0\u00a0\u00a0\u00a03, \u00a0\u00a0\u00a0\u00a0\u00a04,values: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a010, \u00a0\u00a0\u00a0\u00a040, \u00a0\u00a0\u00a0\u00a020, \u00a0\u00a0\u00a0\u00a050, \u00a0\u00a0\u00a0\u00a090,<\/p>
in function make_heap, in DEBUG MODE, printing array after sink_down at index 1.Heap: \u00a0size: 5, capacity : 5indexes: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a00, \u00a0\u00a0\u00a0\u00a0\u00a01, \u00a0\u00a0\u00a0\u00a0\u00a02, \u00a0\u00a0\u00a0\u00a0\u00a03, \u00a0\u00a0\u00a0\u00a0\u00a04,values: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a010, \u00a0\u00a0\u00a0\u00a090, \u00a0\u00a0\u00a0\u00a020, \u00a0\u00a0\u00a0\u00a050, \u00a0\u00a0\u00a0\u00a040,<\/p>
in function make_heap, in DEBUG MODE, printing array after sink_down at index 0.Heap: \u00a0size: 5, capacity : 5indexes: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a00, \u00a0\u00a0\u00a0\u00a0\u00a01, \u00a0\u00a0\u00a0\u00a0\u00a02, \u00a0\u00a0\u00a0\u00a0\u00a03, \u00a0\u00a0\u00a0\u00a0\u00a04,values: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a090, \u00a0\u00a0\u00a0\u00a050, \u00a0\u00a0\u00a0\u00a020, \u00a0\u00a0\u00a0\u00a010, \u00a0\u00a0\u00a0\u00a040,<\/p>
Heap: \u00a0size: 5, capacity : 5indexes: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a00, \u00a0\u00a0\u00a0\u00a0\u00a01, \u00a0\u00a0\u00a0\u00a0\u00a02, \u00a0\u00a0\u00a0\u00a0\u00a03, \u00a0\u00a0\u00a0\u00a0\u00a04,values: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a090, \u00a0\u00a0\u00a0\u00a050, \u00a0\u00a0\u00a0\u00a020, \u00a0\u00a0\u00a0\u00a010, \u00a0\u00a0\u00a0\u00a040,<\/p>
Operation number 1, string: 13add: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a013<\/p>
resizingHeap: \u00a0size: 6, capacity : 10indexes: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a00, \u00a0\u00a0\u00a0\u00a0\u00a01, \u00a0\u00a0\u00a0\u00a0\u00a02, \u00a0\u00a0\u00a0\u00a0\u00a03, \u00a0\u00a0\u00a0\u00a0\u00a04, \u00a0\u00a0\u00a0\u00a0\u00a05,values: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a090, \u00a0\u00a0\u00a0\u00a050, \u00a0\u00a0\u00a0\u00a020, \u00a0\u00a0\u00a0\u00a010, \u00a0\u00a0\u00a0\u00a040, \u00a0\u00a0\u00a0\u00a013,<\/p>
Operation number 2, string: *removed: \u00a0\u00a0\u00a0\u00a090Heap: \u00a0size: 5, capacity : 10indexes: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a00, \u00a0\u00a0\u00a0\u00a0\u00a01, \u00a0\u00a0\u00a0\u00a0\u00a02, \u00a0\u00a0\u00a0\u00a0\u00a03, \u00a0\u00a0\u00a0\u00a0\u00a04,values: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a050, \u00a0\u00a0\u00a0\u00a040, \u00a0\u00a0\u00a0\u00a020, \u00a0\u00a0\u00a0\u00a010, \u00a0\u00a0\u00a0\u00a013,<\/p>
Operation number 3, string: 82add: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a082Heap: \u00a0size: 6, capacity : 10indexes: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a00, \u00a0\u00a0\u00a0\u00a0\u00a01, \u00a0\u00a0\u00a0\u00a0\u00a02, \u00a0\u00a0\u00a0\u00a0\u00a03, \u00a0\u00a0\u00a0\u00a0\u00a04, \u00a0\u00a0\u00a0\u00a0\u00a05,values: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a082, \u00a0\u00a0\u00a0\u00a040, \u00a0\u00a0\u00a0\u00a050, \u00a0\u00a0\u00a0\u00a010, \u00a0\u00a0\u00a0\u00a013, \u00a0\u00a0\u00a0\u00a020,<\/p>
Operation number 4, string: ppeek: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a082Heap: \u00a0size: 6, capacity : 10indexes: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a00, \u00a0\u00a0\u00a0\u00a0\u00a01, \u00a0\u00a0\u00a0\u00a0\u00a02, \u00a0\u00a0\u00a0\u00a0\u00a03, \u00a0\u00a0\u00a0\u00a0\u00a04, \u00a0\u00a0\u00a0\u00a0\u00a05,values: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a082, \u00a0\u00a0\u00a0\u00a040, \u00a0\u00a0\u00a0\u00a050, \u00a0\u00a0\u00a0\u00a010, \u00a0\u00a0\u00a0\u00a013, \u00a0\u00a0\u00a0\u00a020,<\/p>
Operation number 5, string: Ppeek: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a082Heap: \u00a0size: 6, capacity : 10indexes: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a00, \u00a0\u00a0\u00a0\u00a0\u00a01, \u00a0\u00a0\u00a0\u00a0\u00a02, \u00a0\u00a0\u00a0\u00a0\u00a03, \u00a0\u00a0\u00a0\u00a0\u00a04, \u00a0\u00a0\u00a0\u00a0\u00a05,values: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a082, \u00a0\u00a0\u00a0\u00a040, \u00a0\u00a0\u00a0\u00a050, \u00a0\u00a0\u00a0\u00a010, \u00a0\u00a0\u00a0\u00a013, \u00a0\u00a0\u00a0\u00a020,<\/p>
Operation number 6, string: *removed: \u00a0\u00a0\u00a0\u00a082Heap: \u00a0size: 5, capacity : 10indexes: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a00, \u00a0\u00a0\u00a0\u00a0\u00a01, \u00a0\u00a0\u00a0\u00a0\u00a02, \u00a0\u00a0\u00a0\u00a0\u00a03, \u00a0\u00a0\u00a0\u00a0\u00a04,values: \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a050, \u00a0\u00a0\u00a0\u00a040, \u00a0\u00a0\u00a0\u00a020, \u00a0\u00a0\u00a0\u00a010, \u00a0\u00a0\u00a0\u00a013,<\/p>
==170====170== HEAP SUMMARY:==170== \u00a0\u00a0\u00a0\u00a0in use at exit: 0 bytes in 0 blocks==170== \u00a0\u00a0total 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)<\/p><\/code><\/pre>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
\u00a0 Can someone help me with this? \u200b\u200b\u200b\u200b\u200b\u200b\u200b heap.h#ifndef HEAP_H#define HEAP_Hstruct heap_struct {int* items;int N; \u00a0\/\/ current sizeint capacity; \/\/ array capacity};\/\/ max-heap operationsstruct 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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[16],"tags":[],"class_list":["post-99312","post","type-post","status-publish","format-standard","hentry","category-education"],"_links":{"self":[{"href":"https:\/\/assignmenttutors.net\/blog\/wp-json\/wp\/v2\/posts\/99312","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/assignmenttutors.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/assignmenttutors.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/assignmenttutors.net\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/assignmenttutors.net\/blog\/wp-json\/wp\/v2\/comments?post=99312"}],"version-history":[{"count":0,"href":"https:\/\/assignmenttutors.net\/blog\/wp-json\/wp\/v2\/posts\/99312\/revisions"}],"wp:attachment":[{"href":"https:\/\/assignmenttutors.net\/blog\/wp-json\/wp\/v2\/media?parent=99312"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/assignmenttutors.net\/blog\/wp-json\/wp\/v2\/categories?post=99312"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/assignmenttutors.net\/blog\/wp-json\/wp\/v2\/tags?post=99312"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}