A priority queue is a data structure similar to queue in which each element has a certain “priority”, an element with high priority is served before an element with low priority. (container of elements each having an associated key as their priority). The priority of elements determine the order in which elements are removed from the priority queue.
Heap is a binary tree that stores a collection of keys and satisfies two additional properties: a. Structural Property - Complete Binary Tree b. Relational Property - Min Max Heap
Min Heap: For every node v other than the root, key stored at v is greater than or equal to the key stored at v’s parent. Max Heap: For every node v other than the root, key stored at v is less than or equal to the key stored at v’s parent.
The keys encountered on a path from the root to an external node are in a non-decreasing order. A minimum key is always stored at the root. The last node is the right most, deepest external node of the tree.