In this lab, we wil implement min heap ADT, In a min heap, the keys of child nodes are always greater than or equal to those of the parent nodes. The min key is in the root node. In min heap ADT, we will implement two main functions, insert and deleteMin. Additioanlly, we will implement a print function, printHeap.
• Insert: Insert a new key to the min heap. You should find the right position for the new key to maintain the min heap.
• DeleteMin: Delete the min in root node and reconstruct the heap to maintain min heap. If your list does not have any element, just print an error message.
• PrintHeap: Print the entire heap. When printing, each level of the min heap should be printed in a line. If your queue is empty, just print an error message.
1. Input
Obtain a list of operations from the given input file, and execute the given operations in order. A detailed specification of the operations is provided below. Each line represents a single operation. Each operation and the necessary parameters are separated by a space. You may assume that the input values (represented as x below) are any integer.
• n x: create a new heap with the size of x. The number x is the maximum size of the MinHeap. This operation will always be given in the first line of the operations in your input file
• i x: insert a new key “x” into the min heap.
• d : delete the min key in the root node
• p : print the entire min heap. Print each level of the min heap in a line
An input file is shown below.
2. MinHeap ADT
(1) Data Specification for the objects
struct HeapStruct {
int Capacity;
int Size;
ElementType *Elements;
};
(2) Function specification
• HeapStruct* CreateHeap(int heapsize);
• void Insert(HeapStruct heap, ElementType value);
• ElementType DeleteMin(HeapStruct heap);
• void PrintHeap(HeapStruct heap);
3. Program description
• name : p7.c
• input : a list of operations in a file (an input file name is given as a command line argument. See the example in “1. input” on the first page)
• output : the corresponding result in the standard output
Submit to the course git your source code. ( ~2020/5/7 23:59 )
