Data Structures and Algorithms (CS-210)

Lab Session-07
Heap Data Structures and Priority Queues
Dr. M. Abbas Abbasi

1 Objective
Understanding heap data structures and their implementation as priority queues.

2 Learning Outcomes
After completing this lab session, students will be able to:
• Understand the concept and properties of binary heaps
• Implement min-heaps and max-heaps
• Create priority queues using heaps
• Apply basic heap operations (insertion, deletion, extraction)
• Analyze the time complexity of heap operations

3 Heap Data Structure Overview

A heap is a specialized tree-based data structure that satisfies the heap property:
• In a max-heap, for any node N, the value of N is greater than or equal to the values of its children
• In a min-heap, for any node N, the value of N is less than or equal to the values of its children
Heaps are commonly used to implement priority queues, which allow efficient access to the minimum
or maximum element.

3.1 Heap Properties

• Complete Binary Tree: All levels are fully filled except possibly the last level, which is filled
from left to right
• Heap Property: Follows either min-heap or max-heap property
• Efficient Implementation: Can be implemented using arrays without explicit pointers
• Fast Operations: O(log n) for insertion and deletion, O(1) for finding min/max

3.2 Array Representation

Heaps are typically implemented using arrays, where:
• Root is at index 0 (or 1, depending on implementation)
• For a node at index i:
– Left child is at index 2i + 1
– Right child is at index 2i + 2
– Parent is at index (i-1)/2

1
 4 Binary Max-Heap Implementation
1 # include < iostream >
2 # include < vector >
3 using namespace std ;
4

5 class MaxHeap {
6 private :
7 vector < int > heap ;
8

9 // Helper function to get parent index

10 int parent ( int i ) { return ( i - 1) / 2; }
11

12 // Helper function to get left child index

13 int leftChild ( int i ) { return 2 * i + 1; }
14

15 // Helper function to get right child index

16 int rightChild ( int i ) { return 2 * i + 2; }
17

18 // Helper function to maintain heap property ( heapify down )

19 void heapifyDown ( int i ) {
20 int largest = i ;
21 int left = leftChild ( i ) ;
22 int right = rightChild ( i ) ;
23

24 // Compare with left child

25 if ( left < heap . size () && heap [ left ] > heap [ largest ])
26 largest = left ;
27

28 // Compare with right child

29 if ( right < heap . size () && heap [ right ] > heap [ largest ])
30 largest = right ;
31

32 // If largest is not the current node , swap and continue heapifying

33 if ( largest != i ) {
34 swap ( heap [ i ] , heap [ largest ]) ;
35 heapifyDown ( largest ) ;
36 }
37 }
38

39 // Helper function to maintain heap property ( heapify up )

40 void heapifyUp ( int i ) {
41 // If not root and parent is smaller than current node
42 if ( i > 0 && heap [ parent ( i ) ] < heap [ i ]) {
43 swap ( heap [ i ] , heap [ parent ( i ) ]) ;
44 heapifyUp ( parent ( i ) ) ; // Recurse up
45 }
46 }
47

48 public :
49 MaxHeap () {}
50

51 // Insert a new element into the heap

52 void insert ( int key ) {
53 // Add the new key at the end
54 heap . push_back ( key ) ;
55

56 // Fix the max heap property if violated

57 int index = heap . size () - 1;
58 heapifyUp ( index ) ;
59 }
60

61 // Extract the maximum element

2
62 int extractMax () {
63 if ( heap . empty () ) {
64 cout << " Heap is empty ! " << endl ;
65 return -1;
66 }
67

68 // Store the max value to return

69 int max = heap [0];
70

71 // Replace root with last element and remove last element

72 heap [0] = heap . back () ;
73 heap . pop_back () ;
74

75 // Restore max heap property

76 if (! heap . empty () )
77 heapifyDown (0) ;
78

79 return max ;
80 }
81

82 // Get maximum element without removing it

83 int getMax () {
84 if ( heap . empty () ) {
85 cout << " Heap is empty ! " << endl ;
86 return -1;
87 }
88 return heap [0];
89 }
90

91 // Check if heap is empty

92 bool isEmpty () {
93 return heap . empty () ;
94 }
95

96 // Get size of heap

97 int size () {
98 return heap . size () ;
99 }
100

101 // Print the heap

102 void printHeap () {
103 for ( int i = 0; i < heap . size () ; i ++)
104 cout << heap [ i ] << " " ;
105 cout << endl ;
106 }
107 };
108

109 int main () {

110 MaxHeap maxHeap ;
111

112 maxHeap . insert (3) ;

113 maxHeap . insert (2) ;
114 maxHeap . insert (15) ;
115 maxHeap . insert (5) ;
116 maxHeap . insert (4) ;
117 maxHeap . insert (45) ;
118

119 cout << " Max Heap : " ;

120 maxHeap . printHeap () ;
121

122 cout << " Maximum element : " << maxHeap . getMax () << endl ;
123

124 cout << " Extracted max : " << maxHeap . extractMax () << endl ;

3
125 cout << " Max Heap after extraction : " ;
126 maxHeap . printHeap () ;
127

128 return 0;
129 }
Listing 1: Max-Heap Implementation

5 Binary Min-Heap and Priority Queue

1 # include < iostream >
2 # include < vector >
3 using namespace std ;
4

5 class MinHeap {
6 private :
7 vector < int > heap ;
8

9 int parent ( int i ) { return ( i - 1) / 2; }

10 int leftChild ( int i ) { return 2 * i + 1; }
11 int rightChild ( int i ) { return 2 * i + 2; }
12

13 void heapifyDown ( int i ) {

14 int smallest = i ;
15 int left = leftChild ( i ) ;
16 int right = rightChild ( i ) ;
17

18 if ( left < heap . size () && heap [ left ] < heap [ smallest ])
19 smallest = left ;
20

21 if ( right < heap . size () && heap [ right ] < heap [ smallest ])
22 smallest = right ;
23

24 if ( smallest != i ) {
25 swap ( heap [ i ] , heap [ smallest ]) ;
26 heapifyDown ( smallest ) ;
27 }
28 }
29

30 void heapifyUp ( int i ) {

31 if ( i > 0 && heap [ parent ( i ) ] > heap [ i ]) {
32 swap ( heap [ i ] , heap [ parent ( i ) ]) ;
33 heapifyUp ( parent ( i ) ) ;
34 }
35 }
36

37 public :
38 MinHeap () {}
39

40 void insert ( int key ) {

41 heap . push_back ( key ) ;
42 int index = heap . size () - 1;
43 heapifyUp ( index ) ;
44 }
45

46 int extractMin () {
47 if ( heap . empty () ) {
48 cout << " Heap is empty ! " << endl ;
49 return -1;
50 }
51

52 int min = heap [0];

4
53 heap [0] = heap . back () ;
54 heap . pop_back () ;
55

56 if (! heap . empty () )
57 heapifyDown (0) ;
58

59 return min ;
60 }
61

62 int getMin () {
63 if ( heap . empty () ) {
64 cout << " Heap is empty ! " << endl ;
65 return -1;
66 }
67 return heap [0];
68 }
69

70 bool isEmpty () {
71 return heap . empty () ;
72 }
73

74 int size () {
75 return heap . size () ;
76 }
77

78 void printHeap () {
79 for ( int i = 0; i < heap . size () ; i ++)
80 cout << heap [ i ] << " " ;
81 cout << endl ;
82 }
83 };
84

85 int main () {
86 MinHeap minHeap ;
87

88 minHeap . insert (5) ;

89 minHeap . insert (2) ;
90 minHeap . insert (8) ;
91 minHeap . insert (1) ;
92 minHeap . insert (10) ;
93

94 cout << " Min Heap : " ;

95 minHeap . printHeap () ;
96

97 cout << " Minimum element : " << minHeap . getMin () << endl ;
98

99 cout << " Elements extracted in order : " ;

100 while (! minHeap . isEmpty () ) {
101 cout << minHeap . extractMin () << " " ;
102 }
103 cout << endl ;
104

105 return 0;
106 }
Listing 2: Min-Heap Implementation

6 Priority Queue Implementation

1 # include < iostream >
2 # include < vector >
3 using namespace std ;

5
 4

5 // Priority Queue using Min - Heap

6 class PriorityQueue {
7 private :
8 // Pair of value and priority ( lower priority number = higher priority )
9 vector < pair < int , int > > heap ;
10

11 int parent ( int i ) { return ( i - 1) / 2; }

12 int leftChild ( int i ) { return 2 * i + 1; }
13 int rightChild ( int i ) { return 2 * i + 2; }
14

15 void heapifyDown ( int i ) {

16 int smallest = i ;
17 int left = leftChild ( i ) ;
18 int right = rightChild ( i ) ;
19

20 if ( left < heap . size () && heap [ left ]. second < heap [ smallest ]. second )
21 smallest = left ;
22

23 if ( right < heap . size () && heap [ right ]. second < heap [ smallest ]. second )
24 smallest = right ;
25

26 if ( smallest != i ) {
27 swap ( heap [ i ] , heap [ smallest ]) ;
28 heapifyDown ( smallest ) ;
29 }
30 }
31

32 void heapifyUp ( int i ) {

33 if ( i > 0 && heap [ parent ( i ) ]. second > heap [ i ]. second ) {
34 swap ( heap [ i ] , heap [ parent ( i ) ]) ;
35 heapifyUp ( parent ( i ) ) ;
36 }
37 }
38

39 public :
40 PriorityQueue () {}
41

42 // Insert element with priority

43 void enqueue ( int value , int priority ) {
44 heap . push_back ({ value , priority }) ;
45 int index = heap . size () - 1;
46 heapifyUp ( index ) ;
47 }
48

49 // Extract highest priority element ( lowest priority number )

50 int dequeue () {
51 if ( heap . empty () ) {
52 cout << " Priority Queue is empty ! " << endl ;
53 return -1;
54 }
55

56 int value = heap [0]. first ;

57 heap [0] = heap . back () ;
58 heap . pop_back () ;
59

60 if (! heap . empty () )
61 heapifyDown (0) ;
62

63 return value ;
64 }
65

66 // Get highest priority element without removing

6
67 int peek () {
68 if ( heap . empty () ) {
69 cout << " Priority Queue is empty ! " << endl ;
70 return -1;
71 }
72 return heap [0]. first ;
73 }
74

75 bool isEmpty () {
76 return heap . empty () ;
77 }
78

79 int size () {
80 return heap . size () ;
81 }
82

83 void display () {
84 cout << " Priority Queue contents ( value , priority ) : " << endl ;
85 for ( auto & item : heap ) {
86 cout << " ( " << item . first << " , " << item . second << " ) " ;
87 }
88 cout << endl ;
89 }
90 };
91

92 int main () {
93 PriorityQueue pq ;
94

95 // Enqueue elements with priorities ( lower number = higher priority )

96 pq . enqueue (100 , 3) ; // value 100 with priority 3
97 pq . enqueue (200 , 1) ; // value 200 with priority 1
98 pq . enqueue (300 , 4) ; // value 300 with priority 4
99 pq . enqueue (400 , 2) ; // value 400 with priority 2
100

101 pq . display () ;
102

103 cout << " Highest priority element : " << pq . peek () << endl ;
104

105 cout << " Elements dequeued in order of priority : " ;

106 while (! pq . isEmpty () ) {
107 cout << pq . dequeue () << " " ;
108 }
109 cout << endl ;
110

111 return 0;
112 }
Listing 3: Priority Queue Implementation

7 Lab Tasks
Task 1: Basic Heap Operations
Implement a min-heap supporting the following operations:
• Insert elements
• Extract the minimum element
• Decrease the value of a key at a given index
• Build a heap from an array
Test Cases:

7
 1. Insert elements [10, 5, 15, 2, 20]
2. Extract min (should be 2)
3. Decrease the key at index 2 from 15 to 1
4. Extract min (should be 1)
5. Build a heap from [30, 10, 50, 5, 1]
6. Print the resulting min-heap

Task 2: Priority Queue Implementation

Implement a priority queue with the following operations:
• Enqueue element with priority
• Dequeue (extract highest priority element)
• Peek (get highest priority element without removing)
• isEmpty
• size
Test Cases:
1. Create a priority queue
2. Enqueue: (Task A, priority 3), (Task B, priority 1), (Task C, priority 2)
3. Peek (should be Task B)
4. Dequeue (should be Task B)
5. Enqueue: (Task D, priority 1)
6. Dequeue all elements and print them (should be in order: Task D, Task C, Task A)

Task 3: Practical Application

Choose one of the following applications to implement:
Option 1: Process Scheduler
• Create a simple process scheduler using a priority queue
• Each process has an ID, name, and priority
• Implement functions to add processes and execute the highest priority process
• Demonstrate with at least 6 processes of different priorities
Option 2: Top K Elements
• Implement a function to find the k largest elements in an array
• Use a min-heap of size k
• Analyze and explain the time complexity
• Test with different arrays and values of k
Test Cases for Process Scheduler:
1. Add processes with different priorities
2. Execute highest priority process
3. Add more processes during execution
4. Execute all processes and observe the order
Test Cases for Top K Elements:
1. Array: [3, 1, 5, 12, 2, 11], k=3 (should return [5, 11, 12])
2. Array: [5, 15, 10, 20, 8], k=2 (should return [15, 20])
3. Array with duplicate elements