We have presented two asymptotically effcient implementation of a priority queue in this thesis. In the first chapter we have given the definition of priority queue. We have, also, given some additional definitions which we used throughout this thesis. In the second chapter we have analysed and described the implementation of Fibonacci heap. We gave a intuitive description of the implementation of priority queue operations and proved claims needed for the complexity analysis. We, also, briefly describe the complexity analysis method and gave pseudocodes of some operations. We ended the chapter by analysing complexity using the method described in this chapter. In the third chapter we have described and analysed Brodal queue. Firstly, we have described the strict structure of Brodal queue. Then we described a helper data structure called guide. After that, we have described simple tree operations link and delink and implementation of priority queue operations. Finally, we analysed the worst case complexity of implemented operations. In the last chapter, we have compared performance of Fibonacci heap and Brodal queue. We did this by sorting an array of randomly generated numbers using priority queues.