Description
Purpose:
The purpose of this lab is to implement a max-leftist heap class and a max-skew heap class in
C++.
General Requirements:
For this assignment, you will work on a pointer-based implementation of max-leftist heap and
a max-skew heap. (Please refer to slide 7 in note packet 6 for the node structure for leftist
trees.) You are to read in the numbers from a data file of integers and insert each number into a
max-leftist heap (and a max-skew heap). Max-leftist heaps and max-skew heaps can have
duplicate numbers.
For this lab, you should build the heap using the samples which are in the data.txt. After that,
your program should have a simple menu like this:
————————————————————
Please choose one of the following commands:
1- Insert
2- Deletemax
3- Findmax
4- Preorder
5- Inorder
6- Postorder
7- Levelorder
8- Exit
Max-leftist heap:
The max-leftist heap methods should be implemented as follows:
Buildheap() – should build the max-leftist heap using the insert function.
Insert(x) – should insert x into the max-leftist heap using the merge function.
Deletemax() – should delete the maximum value from the max-leftist heap and use the
merge function to merge the remaining two sub heaps.
Findmax() – should return maximum value from the max-leftist heap.
Merge(H1,H2) – merge two max-leftist heaps.
Preorder() should print the preorder traversal of the max-leftist heap.
Inorder() -– should print the inorder traversal of the max-leftist heap.
Postorder() – should print the postorder traversal of the max-leftist heap.
Levelorder() – should print the level order traversal of the max-leftist heap.
Max-skew heap:
The max-skew heap methods should be implemented as follows:
Buildheap() – should build the max-skew heap using the insert function.
Insert(x) – should insert x into the max-skew heap using the merge function.
Deletemax() – should delete the maximum value from the max-skew heap and use the
merge function to merge the remaining two sub heaps.
Findmax() – should return maximum value from the max-skew heap.
Merge(H1,H2) – should merge two max-skew heaps.
Preorder() – should print the preorder traversal of the max-skew heap.
Inorder() – should print the inorder traversal of the max-skew heap.
Postorder() – should print the postorder traversal of the max-skew heap.
Levelorder() – should print the level order traversal of the max-skew heap.
Data file:
data.txt: 11 10 8 5 1 6 2 9 7 3 4
We will insert these values, in the given order, into the max-leftist heap. Note the following
graphical output covers only the max-leftist heap:
Expected output for the max-leftist heap:
————————————————————
Please choose one of the following commands:
1- Insert
2- Deletemax
3- Findmax
4- Preorder
5- Inorder
6- Postorder
7- Levelorder
8- Exit
> 7
11
10 8
9 6 5 1
2 7 3 4
————————————————————
Please choose one of the following commands:
1- Insert
2- Deletemax
3- Findmax
4- Preorder
5- Inorder
6- Postorder
7- Levelorder
8- Exit
> 3
11
————————————————————
Please choose one of the following commands:
1- Insert
2- Deletemax
3- Findmax
4- Preorder
5- Inorder
6- Postorder
7- Levelorder
8- Exit
> 2
Delete max successful
————————————————————
Please choose one of the following commands:
1- Insert
2- Deletemax
3- Findmax
4- Preorder
5- Inorder
6- Postorder
7- Levelorder
8- Exit
> 7
10
9 8
2 7 6 5
3 4
1
————————————————————
Please choose one of the following commands:
1- Insert
2- Deletemax
3- Findmax
4- Preorder
5- Inorder
6- Postorder
7- Levelorder
8- Exit
> 4
10 9 2 7 8 6 3 4 1 5
————————————————————
Please choose one of the following commands:
1- Insert
2- Deletemax
3- Findmax
4- Preorder
5- Inorder
6- Postorder
7- Levelorder
8- Exit
> 1
Integer to Insert: 10
Insert successful
————————————————————
Please choose one of the following commands:
1- Insert
2- Deletemax
3- Findmax
4- Preorder
5- Inorder
6- Postorder
7- Levelorder
8- Exit
> 5
2 9 7 10 3 6 1 4 8 5 10
————————————————————
Please choose one of the following commands:
1- Insert
2- Deletemax
3- Findmax
4- Preorder
5- Inorder
6- Postorder
7- Levelorder
8- Exit
> 2
Delete max successful
————————————————————
Please choose one of the following commands:
1- Insert
2- Deletemax
3- Findmax
4- Preorder
5- Inorder
6- Postorder
7- Levelorder
8- Exit
> 7
10
8 9
6 5 2 7
3 4
1
————————————————————
Please choose one of the following commands:
1- Insert
2- Deletemax
3- Findmax
4- Preorder
5- Inorder
6- Postorder
7- Levelorder
8- Exit
> 6
3 1 4 6 5 8 2 7 9 10
————————————————————
Please choose one of the following commands:
1- Insert
2- Deletemax
3- Findmax
4- Preorder
5- Inorder
6- Postorder
7- Levelorder
8- Exit
> 8
Byebye!
Expected output for max-skew heap:
————————————————————
Please choose one of the following commands:
1- Insert
2- Deletemax
3- Findmax
4- Preorder
5- Inorder
6- Postorder
7- Levelorder
8- Exit
> 7
11
8 10
4 7 6 9
2 1 3 5
————————————————————
Please choose one of the following commands:
1- Insert
2- Deletemax
3- Findmax
4- Preorder
5- Inorder
6- Postorder
7- Levelorder
8- Exit
> 2
Delete max successful
————————————————————
Please choose one of the following commands:
1- Insert
2- Deletemax
3- Findmax
4- Preorder
5- Inorder
6- Postorder
7- Levelorder
8- Exit
> 3
10
————————————————————
Please choose one of the following commands:
1- Insert
2- Deletemax
3- Findmax
4- Preorder
5- Inorder
6- Postorder
7- Levelorder
8- Exit
> 4
10 9 8 4 2 7 1 5 6 3
————————————————————
Please choose one of the following commands:
1- Insert
2- Deletemax
3- Findmax
4- Preorder
5- Inorder
6- Postorder
7- Levelorder
8- Exit
> 1
Integer to insert: 10
Insert successful
————————————————————
Please choose one of the following commands:
1- Insert
2- Deletemax
3- Findmax
4- Preorder
5- Inorder
6- Postorder
7- Levelorder
8- Exit
> 5
3 6 10 10 2 4 8 1 7 9 5
————————————————————
Please choose one of the following commands:
1- Insert
2- Deletemax
3- Findmax
4- Preorder
5- Inorder
6- Postorder
7- Levelorder
8- Exit
> 2
10
9 6
8 5 3
4 7
2 1
————————————————————
Please choose one of the following commands:
1- Insert
2- Deletemax
3- Findmax
4- Preorder
5- Inorder
6- Postorder
7- Levelorder
8- Exit
> 6
2 4 1 7 8 5 9 3 6 10
————————————————————
Please choose one of the following commands:
1- Insert
2- Deletemax
3- Findmax
4- Preorder
5- Inorder
6- Postorder
7- Levelorder
8- Exit
> 8
Byebye!
Submission:
Follow the conventions below to facilitate grading:
Source Code
Place all your source files (*.cpp, *.hpp) and input files in a single folder with no subfolders.
Name your folder using the convention Lastname_LabX (e.g., Smith_Lab010).
Include a functioning Makefile inside the folder. (The makefile should also include the
clean command.)
Verify that your code runs on the lab Linux machines before submission.
Compressed File
Compress using .zip, .rar, or .tar.gz.
Name your file using the convention Lastname_LabX (e.g., Smith_Lab010.zip).
Email
Use the following subject for your email: Lastname_LabX (e.g., Smith_Lab010).
Send your code to l290w868@ku.edu if you are in one of Lei’s sections or to
dhwanipandya1401@ku.edu if you are in one of Dhwani’s sections.
Anytime you have a question about the lab, put the word question in the subject of the
email.
