Heaps

Priority Queues and Heaps

Concept: A Special Kind of Queue A priority queue is an abstract data type that allows us to store elements and retrieve (usually remove) the minimum or maximum element at any time. Unlike a regular queue’s “first-in, first-out” principle, a priority queue outputs the highest-priority element first. An element’s “priority” is typically determined by its value. Comparison with Stack and Queue Structure Order Policy Regular Queue First-In, First-Out (FIFO) — cares about insertion order Stack Last-In, First-Out (LIFO) — also cares about insertion order Priority Queue Highest priority out first — cares about the element’s own priority, regardless of insertion order 1. What Is a Heap? A heap is a special data structure based on a complete binary tree, commonly used to implement priority queues.