CSE 310 Priority Queue

Project Description

Your program will need to define the following data types:

• ELEMENT is a data type that contains a field named key.
  • key is of type int.
  • Note: ELEMENT itself is not of type int.
• HEAP is a data type that contains three fields:
  • capacity is of type int.
  • size is of type int.
  • H is an array of type ELEMENT, with an index ranging from 1 to capacity.

The functions that you are required to implement are:

• initialize(n): returns an object of type HEAP with capacity=n and size=0.
  • This function requires you to perform dynamic memory allocation.
• buildHeap(heap, A, n): where heap is a HEAP object, A is an array of type ELEMENT, n is an int which represents the size of the array A.
  • This function copies the elements of A into heapH (starting from H[1]), and then uses the linear time "build heap algorithm" to obtain a min heap of size n from the given array A (see lecture 05_heaps_heapsort.pptx and Section 6.3 in the book for a max-heap version).
• insert(heap, flag, k): inserts an ELEMENT item with key=k into the min heap heap.
  • if flag==1, the function does not do any printing.
  • if flag==2, the function prints out the heap contents before the insertion, and then prints the heap contents after the insertion.
• deleteMin(heap, flag): deletes the ELEMENT
  • if flag==1, the function does not do any printing.
  • if flag==2, the function prints out the heap contents before the deletion, and then prints out the heap contents after the deletion.
• decreaseKey(heap, flag, index, value): decreases the key of the heap element pointed to by index to the value provided by value.
  • The new key's value will be set by the value parameter, which should not be larger than the current value.
  • Note that you have to make any necessary adjustments to make sure that the "min heap property" is maintained throughout the heap.
  • if flag==1, the function does not do any additional printing.
  • if flag==2, the function prints out the heap contents before the key is decreased, and then prints out the heap contents after the key has been decreased (any any necessary adjustments have been made).
• printHeap(heap): prints out the heap information, including capacity, size, and the key fields of the element in the Harray, with index going from 1 to heap->size.

You should implement a module that takes the following commands from the keyboard and feeds them to the main program: "S", "C n", "R", "W", "I f k", "D f", "K f i v". Reading these do the following:

• S: the program stops.
• C n: the program creates an empty heap with capacity equal to n, and waits for the next command.
• R: the program reads in the array A from the file HEAPinput.txt, calls the linear time build heap algorithm (which builds the min heap based on A), and waits for the next command.
• W: the program writes the current heap information to the screen and waits for the next command. The output should be in the same format as HEAPinput.txt, proceeded by the heap capacity.
• I f k: (capital i-f-k) the program inserts an ELEMENT with key equal to k into the current heap with the corresponding flag set to f, and waits for the next command.
• D f: the program deletes the minimum element from the heap with the corresponding flag set to f, and prints the keyfield of the deleted element on the screen, and waits for the next command.
• K f i v: the program decreases the key of the element with index i to v with the corresponding flag set to f, and waits for the next command.

The file HEAPinput.txt is a text file. The first line of the file contains an integer n, which indicates the number of array elements. The next n lines contain n integers, one per line. These integers are the key values of the n array elements, from the 1st element to the n'th element.