# Cards shuffling. Greedy algorithm

We have n deck of cards. To shuffle i-th deck we need a(i) seconds. Our task is to give a greedy algorithm, which will merge two decks until we have one deck.

My idea is to create a priority queue. At top of the queue we have a minimum value of a(i). And then shuffle Q.top() with the next Q.top() while Q.size() > 1.

Could you help my proving, if it works, or not?

• Yes, it will work. It's same think like Huffman Code – Wojciech Nov 15 '16 at 13:47
• What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. Have you checked our general reference on how to prove greedy algorithms correct? Have you tried applying the methods there? If not, I suggest you work through the material there, try to apply it to your situation, and then edit the question to show us what progress you've made and where specifically you got stuck. – D.W. Nov 15 '16 at 15:36

Find binary rooted tree with $n$ weighted (weights $a_1,...,a_n$) leafs, such that sum of distances from leafs to root multiplied by their weight would be minimal.