Implementing Heaps

We provided you with the starter code for implementing a Minimum Heap. Your task is to implement the functions declared in minheap.h that are not already implemented in minheap.c. Note that minheap.c is the only file you will submit, so make sure your implementation works with the original provided minheap.h. Make sure to carefully study the starter code before you begin to add your own.

Correctness:

HeapNode getMin(MinHeap* heap)

HeapNode extractMin(MinHeap* heap)

void insert(MinHeap* heap, int priority, void* value)

bool decreasePriority(MinHeap* heap, int id, int newPriority)

Program design (modular implementation, self-explanatory code, clear logic, no repeated code, no unnecessary code)

Readability and coding style (good use of white space, good naming, etc.)

You are encouraged (but not required) to use a linter to help check and/or auto-format your code.

The runtime complexity requirements for your functions are as follows:

getMin: constant time.

extractMin: O(log n) time.

insert: If there is space to insert a new node, i.e. heaps size is under its capacity, then this function should run in O(log n) time. Otherwise, this function should double the capacity of the heap, which is O(n) time, and the rest of the insertion algorithm should be O(log n) time.

decreasePriority: O(log n) time.

Starter Code:

====================================minheap.h================================================start below=====

#include #include #include

#ifndef __MinHeap_header #define __MinHeap_header

typedef struct heap_node { int priority; // priority of this node void* value; // value stored in this node int id; // the unique ID of this node, 1 <= id <= size } HeapNode;

typedef struct min_heap { int size; // the number of nodes in this heap int capacity; // the number of nodes that can be stored in this heap HeapNode* arr; // the array that stores the nodes of this heap int* indexMap; // indexMap[id] is the index of node with ID id in array arr } MinHeap;

/* Returns the node with minimum priority in minheap 'heap'. * Precondition: heap is non-empty */ HeapNode getMin(MinHeap* heap);

/* Removes and returns the node with minimum priority in minheap 'heap'. * Precondition: heap is non-empty */ HeapNode extractMin(MinHeap* heap);

/* Inserts a new node with priority 'priority' and value 'value' into minheap * 'heap'. If 'heap' is full, double the capacity of 'heap' before inserting * the new node. */ void insert(MinHeap* heap, int priority, void* value);

/* Sets priority of node with ID 'id' in minheap 'heap' to 'newPriority', if * such a node exists in 'heap' and its priority is larger than * 'newPriority', and returns True. Has no effect and returns False, otherwise. * Note: this function bubbles up the node until the heap property is restored. */ bool decreasePriority(MinHeap* heap, int id, int newPriority);

/* Prints the contents of this heap, including size, capacity, full index * map, and, for each non-empty element of the heap array, that node's ID and * priority. */ void printHeap(MinHeap* heap);

/* Returns a newly created empty minheap with initial capacity 'capacity'. * Precondition: capacity > 0 */ MinHeap* newHeap(int capacity);

/* Frees all memory allocated for minheap 'heap'. */ void deleteHeap(MinHeap* heap);

#endif

====================================minheap.c ========================================start below=====

#include "minheap.h"

#define ROOT_INDEX 1 #define NOTHING -1

/************************************************************************* ** Suggested helper functions *************************************************************************/

/* Swaps contents of heap->arr[index1] and heap->arr[index2] if both 'index1' * and 'index2' are valid indices for minheap 'heap'. Has no effect * otherwise. */ void swap(MinHeap* heap, int index1, int index2);

/* Bubbles up the element newly inserted into minheap 'heap' at index * 'nodeIndex', if 'nodeIndex' is a valid index for heap. Has no effect * otherwise. */ void bubbleUp(MinHeap* heap, int nodeIndex);

/* Bubbles down the element newly inserted into minheap 'heap' at the root, * if it exists. Has no effect otherwise. */ void bubbleDown(MinHeap* heap);

/* Returns the index of the left child of a node at index 'nodeIndex' in * minheap 'heap', if such exists. Returns NOTHING if there is no such left * child. */ int leftIdx(MinHeap* heap, int nodeIndex);

/* Returns the index of the right child of a node at index 'nodeIndex' in * minheap 'heap', if such exists. Returns NOTHING if there is no such right * child. */ int rightIdx(MinHeap* heap, int nodeIndex);

/* Returns the index of the parent of a node at index 'nodeIndex' in minheap * 'heap', if such exists. Returns NOTHING if there is no such parent. */ int parentIdx(MinHeap* heap, int nodeIndex);

/* Returns True if 'maybeIdx' is a valid index in minheap 'heap', and 'heap' * stores an element at that index. Returns False otherwise. */ bool isValidIndex(MinHeap* heap, int maybeIdx);

/* Doubles the capacity of minheap 'heap'. */ void doubleCapacity(MinHeap* heap);

/* Returns priority of node at index 'nodeIndex' in minheap 'heap'. * Precondition: 'nodeIndex' is a valid index in 'heap' * 'heap' is non-empty */ int priorityAt(MinHeap* heap, int nodeIndex);

/********************************************************************* * Required functions ********************************************************************/

/********************************************************************* ** Helper function provided in the starter code *********************************************************************/

void printHeap(MinHeap* heap) { printf("MinHip with size: %d \tcapacity: %d ", heap->size, heap->capacity); printf("index: priority [ID]\t ID: index "); for (int i = ROOT_INDEX; i <= heap->size; i++) printf("%d: %d [%d]\t\t%d: %d ", i, heap->arr[i].priority, heap->arr[i].id, i, heap->indexMap[i]); for (int i = heap->size + 1; i <= heap->capacity; i++) printf("\t\t\t%d: %d ", i, heap->indexMap[i]); printf(" "); }

/********************************************************************* ** Helper functions not provided in the starter code *********************************************************************/

====================================minheap_tester.c ========================================start below=====

#include #include #include

#include "minheap.h"

#define MAX_LIMIT 1024 #define DEFAULT_CAPACITY 5

MinHeap* createHeap(FILE* f); void testHeap(MinHeap* heap); void printHeapReport(MinHeap* heap);

int main(int argc, char* argv[]) { MinHeap* heap = NULL;

// If user specified a file for reading, create a heap with priorities from // it. if (argc > 1) { FILE* f = fopen(argv[1], "r"); if (f == NULL) { fprintf(stderr, "Unable to open the specified input file: %s ", argv[1]); exit(0); } heap = createHeap(f); fclose(f); } else { printf("You did not specify an input file."); printf(" We will start with an empty heap of default capacity %d. ", DEFAULT_CAPACITY); heap = newHeap(DEFAULT_CAPACITY); }

testHeap(heap); return 0; }

MinHeap* createHeap(FILE* f) { char line[MAX_LIMIT]; int priority = 0; MinHeap* heap = newHeap(DEFAULT_CAPACITY);

while (fgets(&line[0], MAX_LIMIT, f)) { // read the next line priority = atoi(&line[0]); printf("read %d ", priority); insert(heap, priority, NULL); // no values for this simple tester printHeapReport(heap); } return heap; }

void testHeap(MinHeap* heap) { char line[MAX_LIMIT]; HeapNode node; int id = 0;

while (1) { printf("Choose a command: (g)et-min, (e)xtract-min, (i)nsert, "); printf("(d)ecrease-priority, (q)uit "); fgets(&line[0], MAX_LIMIT, stdin); if (line[0] == 'q') { // quit printf("quit selected. Goodbye! "); deleteHeap(heap); return; } if (line[0] == 'g') { // get-min printf("get-min selected. "); if (heap->size == 0) { printf("Heap is empty: can't get min. Choose another command. "); continue; } node = getMin(heap); printf("Minimum is priority %d of node with ID %d. ", node.priority, node.id); } else if (line[0] == 'e') { // extract-min printf("extract-min selected. "); if (heap->size == 0) { printf("Heap is empty: can't extract min. Choose another command. "); continue; } node = extractMin(heap); printf("Minimum was priority %d of node with ID %d. ", node.priority, node.id); printHeapReport(heap); } else if (line[0] == 'i') { // insert printf("insert selected. Enter priority to insert"); printf(" (no values in this simple tester): "); fgets(&line[0], MAX_LIMIT, stdin); insert(heap, atoi(&line[0]), NULL); printHeapReport(heap); } else if (line[0] == 'd') { // decrease-priority printf("decrease-priority selected. Enter node ID: "); fgets(&line[0], MAX_LIMIT, stdin); id = atoi(&line[0]); printf("decrease-priority selected. Enter node new priority: "); fgets(&line[0], MAX_LIMIT, stdin); if (decreasePriority(heap, id, atoi(&line[0]))) { printHeapReport(heap); } else { printf("Either there was no such node in the heap or the new priority"); printf(" is no smaller than the node's priority."); printf(" No change has been made. "); } } } }

void printHeapReport(MinHeap* heap) { printf("** The heap is now: "); printHeap(heap); printf("** "); } ====================================sample_input.txt.c ========================================start below=====

9 1 8 2 5 3 7 8 4 3 6 8