Implementing a Mini-heap Using a Dynamic Array
Implement a mini-heap using a dynamic array implementation. The class should be named SongHeap, and it uses the same dataset as in PA 3 (Billboard Top 100). Write all basic class functions (default and copy constructors, destructor, copy homework).
SongHeap Class
SongHeap has a data member songList, which is an array of Songs. Set the initial size of songList to 5, and double the size as needed. A Song is similar to a TreeNode in PA 3. The song title acts as a key, and smaller keys have higher priority (ex. “A” before “B”).
struct Song{
string title; //used as key
string artist;
string dates[52]; //filled starting from index 0
int frequency; //should match # of elements in dates
};
Heap Functions
Implement the following functions:
1. void insert(string title, string artist, string date). You should first check all the songs in songList to see if the song is already in the heap. If so, update the frequency and dates of the Song. Otherwise, create and add a Song to the heap (i.e., songList). The heap should grow as needed.
2. string deleteMin(): deletes the Song with the min key and returns its title.
3. print(): prints all the songs in the heap using the following format – arr[i]: title (See the execution example).
4.printSong(string title): finds and prints all the information about the song.
Code Testing and submission
Provide a driver/client program to demonstrate your functions. You can create a SongHeap and add all the songs in top1.csv to the heap, similarly to how you read in the file for PA 3. Test ALL the functions thoroughly in the driver, including all the edge cases.
Submit your program using the following command:
/home/fac/hkong/submit/cpsc2430/submit_pa4
The SongHeap class should be in two files named songheap.h and songheap.cpp. The driver should be in a file named pa4.cpp.
Code Solution
[PA4]./pa4
Hello! Processing the first 30 lines of top1.csv file.
The array is full. Resizing array to 10 elements.
The array is full. Resizing array to 20 elements.
Printing tree:
arr[1] = All I Want For Christmas Is You arr[2] = Blinding Lights
arr[3] = Say So
arr[4] = Circles
arr[5] = Rain On Me
arr[6] = The Scotts
arr[7] = The Box
arr[8] = Stuck With U
arr[9] = Savage
arr[10] = Toosie Slide
arr[11] = Rockstar
arr[12] = Trollz
Which song do you want to print? Blinding Lights
Title: Blinding Lights
Artist: The Weeknd
Appeared on the Billboard chart 4 times on:
2020-04-11
2020-04-18
2020-05-02
2020-05-09
Which song do you want to print? Testing Testing is not in the heap.
Removing the min value. "All I Want For Christmas Is You" has been removed.
Printing the updated heap:
arr[1] = Blinding Lights
arr[2] = Circles
arr[3] = Say So
arr[4] = Savage
arr[5] = Rain On Me
arr[6] = The Scotts
arr[7] = The Box
arr[8] = Stuck With U
arr[9] = Trollz
arr[10] = Toosie Slide
arr[11] = Rockstar
Removing the min value. "Blinding Lights" has been removed.
Printing the updated heap:
arr[1] = Circles
arr[2] = Rain On Me
arr[3] = Say So
arr[4] = Savage
arr[5] = Rockstar
arr[6] = The Scotts
arr[7] = The Box
arr[8] = Stuck With U
arr[9] = Trollz
arr[10] = Toosie Slide
This is the end of the execution example. Goodbye!