Should PriorityQueue actually be a dictionary?

Currently, PriorityQueue is implemented as an AbstractDict by wrapping a Dict instance. Apparently, this design mixes two different data structures, and since this leads to performance issues (e.g., https://github.com/JuliaCollections/DataStructures.jl/issues/596) I'm wondering if this should be changed.

Instead, alternatively PriorityQueue could be implemented as a wrapper of a heap structure for pairs (by default a BinaryHeap but adjustable by the user) that provides a consistent interface for accessing the top element, its key and its value, removing the top element, and inserting elements, without additionally serving as a dictionary (similar to, e.g., the std::priority_queue in C++). If users need a dictionary structure as well, they can create one independently of the PriorityQueue. This separation would also make it easier to use alternative dictionary types such as SwissDict or RobinDict.

Start by reading the current PriorityQueue implementation and the linked performance discussion. Compare the AbstractDict/Dict design with the proposed BinaryHeap-backed interface, then establish the intended API and compatibility expectations before implementation; done requires an agreed design and corresponding behavior and performance validation.