search
Log In
0 votes
37 views
Give an $O(n\lg\ k)$- time algorithm to merge $k$ sorted lists into one sorted list, where $n$ is the total number of elements in all the input lists. (Hint: Use a minheap for $k$-way merging.)
in Algorithms 37 views

Please log in or register to answer this question.

Related questions

0 votes
1 answer
1
72 views
The operation HEAP-DELETE$(A, i)$ deletes the item in node $i$ from heap $A$. Give an implementation of HEAP-DELETE that runs in $O(lg\ n)$ time for an $n-$element max-heap.
asked Jun 27, 2019 in Algorithms akash.dinkar12 72 views
0 votes
0 answers
2
41 views
Show how to implement a first-in, first-out queue with a priority queue. Show how to implement a stack with a priority queue.
asked Jun 27, 2019 in Algorithms akash.dinkar12 41 views
0 votes
0 answers
3
31 views
Each exchange operation on line $5$ of HEAP-INCREASE-KEY typically requires three assignments. Show how to use the idea of the inner loop of INSERTION-SORT to reduce the three assignments down to just one assignment.
asked Jun 27, 2019 in Algorithms akash.dinkar12 31 views
0 votes
0 answers
4
22 views
Argue the correctness of HEAP-INCREASE-KEY using the following loop invariant: At the start of each iteration of the while loop of lines $4-6$, the subarray $A[1..A.heapsize]$ satisfies the max-heap property, except that there may be one violation$::$ $A[i]$ may be ... $A[a..heapsize]$ satisfies the max-heap property at the time HEAP-INCREASE-KEY is called.
asked Jun 27, 2019 in Algorithms akash.dinkar12 22 views
...