Heap and Priority Queue
Table of Contents
1 Introduction to Heap and Priority Queue
A heap is a tree-based data structure that adheres to the heap property: in a max heap, any parent node's key (value) is greater than or equal to the keys of its children. Conversely, in a min heap, the key of a parent node is less than or equal to the keys of its children.
For more details, refer to Wikipedia: Heap (data structure).
A priority queue is an abstract data type similar to a regular queue or stack, where each element has an associated priority. Elements with higher priority are served before those with lower priority.
For more details, refer to Wikipedia: Priority queue.
Although they are conceptually different, priority queues are often referred to as heaps because they are commonly implemented using heaps.
The binary heap is a data structure that efficiently supports the basic priority queue operations. It allows O(1) performance for accessing the root, O(log n) for insertions and deletions, and O(n) for initially building the heap from a set of n elements.
Note that the time complexity to build a heap is O(n log n) using a top-down approach, whereas a bottom-up approach achieves O(n).
