In: Computer Science
DATA STRUCTURES:
For each algorithm, always explain how and why they work. If not by a proof, at least by a clear explanation. ALWAYS, analyze the running time complexity of your algorithms. Do not write a program. Write pseudo codes or explain in words
Q1: We want to maintain both a Queue and a Priority Queue. When you do Enqueue you also add the item to the Priority Queue and when you do Dequeue you also remove the item from the Priority Queue. And vise-versa. Show how to do it.
Q2: Give a data structure that implements a Min-Heap and the command Max(S) that returns the maximum in the heap. Try and make the last operation as fast as possible.
Q3: (a)Show how to implement a Queue by a Priority Queue. What is the run time per operation?
(b Show how to implement a Stack using Priority Queue. What is the run time per operation?
SOLUTION:
CONSIDERING THE CONDITIONS AND REQUIREMENTS FROM THE QUESTION
THUS THE PSEUDO CODES FOR SET OF QUESTIONS ARE:
QUESTION 1:
Say that we want to maintain both a Queue and a Priority Queue. This means that when you do Enqueue you also add the item to the Priority Queue and when you do Dequeue you also remove the item from the Priority Queue. And vise-versa. Show how to do it.
ans:
it is just an extension of queue
It properties incluude:
Every item has its own priority
first of all low priority element is dequeued and then high
priority element will be dequeued
If two elements have the same priority, it will be treated
according to order of sequence
insert(item, priority): This adds an item
getHighestPriority(): it shows item which has highest
priority
deleteHighestPriority(): it deletes an item which has highest
priority
QUESTION 2:
Give a data structure that implements a Min-Heap and the command Max(S) that returns the maximum in the heap. Try and make the last operation as fast as possible.
ans:
Input : 15
/ \
20 22
/ \ / \
44 31 59 41
Output : 59
Input : 10
/ \
30 18
Output : 30
ans:
QUESTION 3:
1. Show how to implement a Queue by a Priority Queue. What is the run time per operation?
2. Show how to implement a Stack using Priority Queue. What is the run time per operation?
ans:It can be implemented using many common data structures
1)Using Array:
struct item {
int item;
int priority;
}
2)here , elements are assigned with a priority and then pushed. A
stack requires elements to be processed it follows LIFO rule. The
idea is to associate a count that determines when it was pushed. it
just work as a key for the priority queue.So the implementation of
stack uses a priority queue of pairs, 1st element is considered to
be key.
NOTE: PLEASE UPVOTE ITS VERY MUCH NECESSARY FOR ME A LOT. PLZZZZ.....