Heaps and priority queues are grouped together because they are not two different concepts at the same level—they are tightly coupled abstraction + implementation.

Core Relationship

• Priority Queue → Abstract Data Type (ADT)
• Heap → Concrete Data Structure (implementation)

Meaning

• A priority queue defines what you want to do:
  • insert elements
  • remove highest/lowest priority
• A heap defines how you efficiently do it

What is a Priority Queue?

Definition

A data structure where each element has a priority, and you always remove the element with:

• highest priority (max PQ), or
• lowest priority (min PQ)

Operations

• insert(x)
• peek() → get best element
• pop() → remove best element

What is a Heap?