CareerCup

HeapSort

HeapSort

A priority queue is a max/min heap itself. If you insert all the elements into a priority queue and dequeue one by one, the output will automatically sorted. This way you just need one priority queue and O(nlogn) time complexity.

If we need to use two queues, then insert half of the array to each queue, then dequeue them following the "merge" method in merge sort. But I don't think it will be faster this way.

If you have to solve with two queues, you will need a max and min Queue.
After inserting, you will need to exchange elements to keep both queues with the same number of elements as possible.

Use the mediam to determine where you should insert.

Another solution:
1. build a min PQ A
2. get the root node[1] from A, remember its index i and insert it to second min PQ B
3. delete the node[i] from B(the smallest one)
4. get two children of node[i] from A, remember their indexes and insert them to B
5. repeat 3-4 to get the half sorted array
6. sort down the remaining half items