What is the most appropriate data structure to implement a priority queue ?
Heap is the best implementation of Priority Queue.
Read this and this