please I need help with this Qs: 1- Write an algorithm in pseudo-code for findin

Question

please I need help with this Qs:
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

STACK-EMPTY ( )

       1. first = queue 1 for enqueue

       2. second = queue 2 for dequeue

Push (value)   // PUSH function

   1. Enqueue (value, first)

pop ( )    // POP function

    1. for i = 1 to size.fist -1

    2. enqueue(dequeue.first, second)

    3. value = dequeue.first

    4. for i = 1 to size.second - 1

    5. enqueue(dequeue.second, first)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.