I need help with these Qs. I have a test on them. 1. Write an algorithm in pseud
ID: 3623480 • Letter: I
Question
I need help with these Qs. I have a test on them.1. Write an algorithm in pseudo-code for finding the k largest elements from a set of n elements, using heap properties and functions, and show that its time T(n)= O(n+k·lg(n)).
How large can k be, as a function of n, where its T(n)= O(n)?
Hint: use the functions BuildMaxHeap() on p.157 and at least the first 4 lines of Heapsort() on page160.
2. Show how to obtain the functions of stacks and simple queues using priority queues based on heaps. Explain how keys can be assigned to the elements so that a largest-in-first-out procedure is the same as a first-in-first-out procedure.
The priority queue functions are listed on page 162.
The stack functions (pages 232-233) are: StackEmpty(S), Push(S, element), Pop(S).
The simple queue functions (pages 234-235) are: Enqueue(Q, element), Dequeue(Q).
3. Read http://en.wikipedia.org/wiki/Heapsort. Does the MaxHeapify() pseudo-code on page 154 correspond to the siftDown() or the siftUp() functions? Briefly explain why.
Explanation / Answer
Dear user, 2) Take the priority queue function: A priority queue is a data structure for maintaining a set S of elements, each with an assoicated value called a key. A max-priority queue supports the following operations. INSERT(S,x) inserts the elements x into the set S. This operation coule be written as S<-S U {x}. MAXIMUM(S) returns the element of S with the largest key. EXTRACT-MAX(S) removes and returns the element of S with the largest key. INCREASE-KEY(S,x,k) increases the value of element x's key to the new value k, which is assumed to be at least as large as x's current key value. Use largest-in-first-out procedure can be implemented by using a min-priority queue. A priority queue is a data structure for maintaining a set S of elements, each with an assoicated value called a key. A max-priority queue supports the following operations. INSERT(S,x) inserts the elements x into the set S. This operation coule be written as S<-S U {x}. MAXIMUM(S) returns the element of S with the largest key. EXTRACT-MAX(S) removes and returns the element of S with the largest key. INCREASE-KEY(S,x,k) increases the value of element x's key to the new value k, which is assumed to be at least as large as x's current key value. Use largest-in-first-out procedure can be implemented by using a min-priority queue. Here, initialized to 0 and use a counter k to denote the number of elements in the queue,Use another counter 1 to denote the number of elements removed from the queue initialize to 0. Whenever a new element comes in, assign it priority k and add it to the queue, k<-k+1, running time (1), since the newly added element has the maximum priority and thus stay at the last position. Whenever a new element comes in assign it priority k and it to the queue k<-k+1. Worst case running time (log k). Since, the newly added element has the maximum priority and thus to be pop up the root. Whenever an element is removed from the queue, k<- k-1 then running time (log(k-1).Since one max-heapify required. Note: One question per one post regarding cramster rules