Oh yes! So the N log N solution is the intended one :)
And oh yes, definitely! We had the heaps DS as a part of our course last semester, but I guess this is the first time i'm practically solving a CP problem using their STL version of Priority Queues!
And I really would like to thank you for your patience in replying to all of my queries bro! Cheers!