Please help. Explanations would be helpful too. 1.)How to implement the Stack AD
ID: 673748 • Letter: P
Question
Please help. Explanations would be helpful too.
1.)How to implement the Stack ADT using only a priority queue? Implement only Push and Pop .
2.)How to implement the Queue ADT using only a priority queue? Implement only enQueue and Dequeue.
3.)How to implement the Priority Queue ADT using only two queues? Implement only removeMin and insert.
4.)Suppose that an applicaton that uses a priority queue will have a very large number of insertions and a very small number of removeMin calls. How would you implement the priority queue (sorted list, unsorted list, or heap)?
B.)Write a linear algorithm that checks if an array A of n elements contains a vector-based heap.
C.)Draw a heap where the pre-order traversal lists the elements in increasing order.
D.)Draw a heap where the pre-order traversal does NOT lists the elements in increasing order.
E.)Is an array A that is sorted in increasing order a vector-based heap? Ignore A[0].
Explanation / Answer
>>>>>>>>>>>
1) Pseudocode:
class Stack
{
class Element { int prio, Key elem; };
MaxPriorityQueue<Element> q;
int top_priority = 0;
void push(Key x) { q.push(Element(top_priority++, x)); }
Key pop() { top_priority--; return q.pop().elem; }
};
The LIFO behavior follows from the fact that every new element is pushed with a priority higher than all the current elements, so it will be popped before any of them.
-------------------------------------------------------------------------------------------------------------------------
c)
>>>>
See the following pattern as the number of children increase:
-If number of children is 2 the split is: (1, 1)
-If number of children is 3 the split is: (2, 1)
Continuing this way when the number of children is between 2 and 6 we get the following splits:
(1, 1), (2, 1), (3, 1), (3, 2), (3, 3)
When the number of children is between 6 and 14 we get:
(3, 3), (4, 3), (5, 3), (6, 3), (7, 3), (7,4), (7, 5), (7, 6), (7, 7)
>>>>
So when the number of children is between (2^k-2) and (2^{k+1}-2) we get:
either a split of the form (2^{k-1}-1+l, 2^{k-1}-1) where 0 <= l <= 2^{k-1} or
(2^k-1, 2^{k-1}-1+l) where 0 <= l <= 2^{k-1}
The logic then would be to find a k such that (2^k-2) <= childCount <= (2^{k+1}-2) and split as follows:
>>>>
Let l = childCount - (2^k-2)
If l <= 2^{k-1}
split with (2^{k-1}-1+l, remaining)
Else
split with (2^k-1, remaining)
--------------------------------------------------------------------------------
D)
This is possible for BSTs, but not for trees in general.
Let us demonstrate with the given BST:
_ 6 _
/
_4_ _8_
/ /
2 5 7 10
The preorder traversal is {6, 4, 2, 5, 8, 7, 10}.
>>>
This method is to simply create an empty BST and insert the elements in the list one by one. Insertion into a BST takes care of placing the elements in the right order, and since we know that the original tree was a BST, there is only one way for it to produce the list when doing preorder traversal.
t = new Tree()
t.insert(6)
_ 6 _
/
t.insert(4)
_ 6 _
/
4
t.insert(2)
_ 6 _
/
_4_
/
2
t.insert(5)
_ 6 _
/
_4_
/
2 5
t.insert(8)
_ 6 _
/
_4_ 8
/
2 5
and so on for the rest of the values. Below is the algorithm written in Java:
BST construct_BST(int[] preorder) {
BST t = new BST();
for (int i=0; i<preorder.length; i++) {
t.insert(preorder[i]);
}
return t;
}
Unbalanced BSTs are no problem, see for instance:
1 4
/
2 3
/
3 2
/
4 1
preorder: preorder:
{1,2,3,4} {4,3,2,1}
When we add the nodes in the order from the list, it becomes unbalanced just like the original BST was.