Heap as Priority Queue | Data Structures & Algorithms
Heap as Priority Queue
Data Structures & Algorithms | Complete Study Notes
1. Introduction to Priority Queue
1.1 What is a Priority Queue?
A priority queue is an abstract data type (ADT) in which each element is associated with a priority,
and elements are served based on their priority instead of their insertion order.
• Higher priority element → served first
• Same priority → served according to FIFO (queue behavior)
Real-Life Examples: Hospital emergency room → critical patients treated first | CPU
scheduling → high-priority processes executed first
1.2 Types of Priority Queues
1. Max Priority Queue
• Highest priority element is removed first
• Uses Max Heap
2. Min Priority Queue
• Lowest priority element is removed first
• Uses Min Heap
2. Heap Data Structure Overview
2.1 What is a Heap?
A heap is a complete binary tree that satisfies the heap property.
2.2 Heap Properties
3. Shape Property
• Must be a complete binary tree
• All levels filled except possibly the last
4. Heap Order Property
• Max Heap: Parent ≥ Children
• Min Heap: Parent ≤ Children
2.3 Array Representation of Heap
Heaps are efficiently stored using arrays:
DSA Notes | Page 1 of 6
, Heap as Priority Queue | Data Structures & Algorithms
• Parent index = ⌊i/2⌋
• Left child = 2i
• Right child = 2i + 1
This avoids pointer overhead and improves cache performance.
3. Why Heap is Ideal for Priority Queue
3.1 Efficiency Comparison
Operation Unsorted Array Sorted Array Heap
Insert O(1) O(n) O(log n)
Delete (max/min) O(n) O(1) O(log n)
Heap provides balanced performance for both insertion and deletion.
3.2 Key Operations in Heap-based Priority Queue
5. Insert (enqueue with priority)
6. Delete (remove highest/lowest priority)
7. Peek (get top element)
4. Heap Operations in Priority Queue
4.1 Insertion (Heapify Up)
Concept
• Insert element at the end
• Compare with parent
• Swap until heap property is restored
Example: Insert 10, 20, 5
• Insert 10 → becomes root
• Insert 20 → swap with 10 → 20 becomes root
• Insert 5 → no swap needed
DSA Notes | Page 2 of 6
Heap as Priority Queue
Data Structures & Algorithms | Complete Study Notes
1. Introduction to Priority Queue
1.1 What is a Priority Queue?
A priority queue is an abstract data type (ADT) in which each element is associated with a priority,
and elements are served based on their priority instead of their insertion order.
• Higher priority element → served first
• Same priority → served according to FIFO (queue behavior)
Real-Life Examples: Hospital emergency room → critical patients treated first | CPU
scheduling → high-priority processes executed first
1.2 Types of Priority Queues
1. Max Priority Queue
• Highest priority element is removed first
• Uses Max Heap
2. Min Priority Queue
• Lowest priority element is removed first
• Uses Min Heap
2. Heap Data Structure Overview
2.1 What is a Heap?
A heap is a complete binary tree that satisfies the heap property.
2.2 Heap Properties
3. Shape Property
• Must be a complete binary tree
• All levels filled except possibly the last
4. Heap Order Property
• Max Heap: Parent ≥ Children
• Min Heap: Parent ≤ Children
2.3 Array Representation of Heap
Heaps are efficiently stored using arrays:
DSA Notes | Page 1 of 6
, Heap as Priority Queue | Data Structures & Algorithms
• Parent index = ⌊i/2⌋
• Left child = 2i
• Right child = 2i + 1
This avoids pointer overhead and improves cache performance.
3. Why Heap is Ideal for Priority Queue
3.1 Efficiency Comparison
Operation Unsorted Array Sorted Array Heap
Insert O(1) O(n) O(log n)
Delete (max/min) O(n) O(1) O(log n)
Heap provides balanced performance for both insertion and deletion.
3.2 Key Operations in Heap-based Priority Queue
5. Insert (enqueue with priority)
6. Delete (remove highest/lowest priority)
7. Peek (get top element)
4. Heap Operations in Priority Queue
4.1 Insertion (Heapify Up)
Concept
• Insert element at the end
• Compare with parent
• Swap until heap property is restored
Example: Insert 10, 20, 5
• Insert 10 → becomes root
• Insert 20 → swap with 10 → 20 becomes root
• Insert 5 → no swap needed
DSA Notes | Page 2 of 6
