Data Structures - Homework Topics covered: Heaps and Priority Queues Objective:
ID: 3706845 • Letter: D
Question
Data Structures - Homework Topics covered: Heaps and Priority Queues Objective: The objective of this Assignment is to create an implementation of a Heap and a Priority Queue Task 1: Create an implementation of a Priory queue using a sorted linked list class. Include the tollowing members: 1. a. Insert This will add an item to the queue in the appropriate location. b. Remove - This will remove an item from the queue from the appropriate location. c. PrintQueue- This will print the items in the queue in priority order 2. Create a menu for testing the queue. 3. In the report, discuss the advantages and disadvantages of this structure over a standard queue Task 2: 1. Create an implementation of a Heap using a class. Include the following members: a. Insert -This will add an item to the queue in the appropriate location. b. Remove This will remove an item from the queue from the appropriate location. c. PrintHeap- This will print the items in the heap in priority order Create a menu for testing the Heap. In the report, discuss the advantages and disadvantages of this structure over a standard binary search tree. 2. 3. Task 3 1. Evaluate the performance of adding 500, 1,000, 2,000, and 5,000 random items to each of the structures built in task 1 and 2 using the same techniques as the sorting lab. Make sure the items being added are the same for each of the structures. In the report, graph the results and discuss the performance of each structure compared to the expected performance from Big O notation. Evaluate the performance of removing all of the items from step 1 for each of the 4 sets of data (remove 1 at a time, not all at once). Make sure the items being added are the same for each of the structures. In the report, graph the results and discuss the performance of each structure compared to the expected performance from Big O notation. 2.Explanation / Answer
task 1: ,.......................priority queue using sorted linked list................................
#include<stdio.h>
#include<stdlib.h>
struct node
{
int val, pr;
struct node *next;
}*start; //start is declared
// fuction to print queue items
void printqueue()
{
struct node *temp;
temp = start;
printf(" Priority Queue: ");
while(temp!=NULL)
{
printf("%d,%d ",temp->val, temp->pr);
temp=temp->next;
}
printf(" ");
}
// inserting an item into queue
void insert(int ele,int pri)
{
struct node *temp, *t;
temp = (struct node *)malloc(sizeof(struct node));
temp->val=ele;
temp->pr=pri;
temp->next=NULL;
if(start==NULL)
start = temp;
else if(start->pr>pri)
{
temp->next=start;
start=temp;
}
else
{
t=start;
while(t->next!=NULL && (t->next)->pr<=pri )
t=t->next;
temp->next=t->next;
t->next=temp;
}
printqueue();
}
//removing an item from queue ,
void removel()
{
if(start!=NULL)
{
printf(" Removed: %d",start->val);
start = start->next;
printqueue();
}
else
printf(" Error List Empty");
}
// menu for testing the queue
int main()
{
int ch, ele, pr, check=1;
while(check==1)
{
printf(" In Priority Queue Select: 1. Insert 2. Remove 3. Exit ");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf(" Enter element and its priority: ");
scanf("%d%d",&ele,&pr); //input from user
insert(ele,pr); //Send Element and its priority for insertion
break;
case 2:
removel();
break;
case 3:
check=0; //Stops the loop
break;
default:
printf("Wrong Choice");
printf(" Press 1 to continue or 0 to stop");
scanf("%d",&check);
}
}
return 0;
} //end of Main
Task 2: .................................heap sort...................................................
#include <stdio.h>
int array[100], n;
// menu for testing heap
main()
{
int choice, num;
n = 0;/*Represents number of nodes in the heap*/
while(1)
{
printf("1.Insert the element ");
printf("2.Delete the element ");
printf("3.Display all elements ");
printf("4.Quit ");
printf("Enter your choice : ");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("Enter the element to be inserted to the list : ");
scanf("%d", &num);
insert(num, n);
n = n + 1;
break;
case 2:
printf("Enter the elements to be deleted from the list: ");
scanf("%d", &num);
delete(num);
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf("Invalid choice ");
}/*End of switch */
}/*End of while */
}/*End of main()*/
// printing heap elememts
display()
{
int i;
if (n == 0)
{
printf("Heap is empty ");
return;
}
for (i = 0; i < n; i++)
printf("%d ", array[i]);
printf(" ");
}/*End of display()*/
// inserting an element into heap
insert(int num, int location)
{
int parentnode;
while (location > 0)
{
parentnode =(location - 1)/2;
if (num <= array[parentnode])
{
array[location] = num;
return;
}
array[location] = array[parentnode];
location = parentnode;
}/*End of while*/
array[0] = num;
}/*End of insert()*/
// deleting an element from heap
delete(int num)
{
int left, right, i, temp, parentnode;
for (i = 0; i < num; i++) {
if (num == array[i])
break;
}
if (num != array[i])
{
printf("%d not found in heap list ", num);
return;
}
array[i] = array[n - 1];
n = n - 1;
parentnode =(i - 1) / 2; /*find parentnode of node i */
if (array[i] > array[parentnode])
{
insert(array[i], i);
return;
}
left = 2 * i + 1; /*left child of i*/
right = 2 * i + 2; /* right child of i*/
while (right < n)
{
if (array[i] >= array[left] && array[i] >= array[right])
return;
if (array[right] <= array[left])
{
temp = array[i];
array[i] = array[left];
array[left] = temp;
i = left;
}
else
{
temp = array[i];
array[i] = array[right];
array[right] = temp;
i = right;
}
left = 2 * i + 1;
right = 2 * i + 2;
}/*End of while*/
if (left == n - 1 && array[i]) {
temp = array[i];
array[i] = array[left];
array[left] = temp;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.