Unit 4: Priority Queues I M.

Tech (CSE) - I Sem

PriorityQueue

The PriorityQueue class provides the functionality of the heap data structure. It implements the Queue
interface.

Unlike normal queues, priority queue elements are retrieved in sorted order.
Suppose, we want to retrieve elements in the ascending order. In this case, the head of the priority queue
will be the smallest element. Once this element is retrieved, the next smallest element will be the head of
the queue.
It is important to note that the elements of a priority queue may not be sorted. However, elements
are always retrieved in sorted order.
There are two types of priority queues:
 Min priority queue
 Max priority queue
Min priority queue: Collection of elements in which the items can be inserted arbitrarily, but only
smallest element can be removed.
Max priority queue: Collection of elements in which insertion of items can be in any order but only
largest element can be removed.
In priority queue, the elements are arranged in any order and out of which only the smallest or largest
element allowed to delete each time.
The implementation of priority queue can be done using arrays or linked list.
The data structure heap is used to implement the priority queue effectively.
APPLICATIONS:
 The typical example of priority queue is scheduling the jobs in operating system. Typically OS
allocates priority to jobs. The jobs are placed in the queue and position of the job in priority
queue determines their priority. In OS there are 3 jobs- real time jobs, foreground jobs and
background jobs. The OS always schedules the real time jobs first. If there is no real time jobs
pending then it schedules foreground jobs. Lastly if no real time and foreground jobs are pending
then OS schedules the background jobs.
 In network communication, the manage limited bandwidth for transmission the priority queue is
used.
 In simulation modeling to manage the discrete events the priority queue is used.
Various operations that can be performed on priority queue are
1. Find an element
2. Insert a new element

VLITS, Vadlamudi. Page 1

 Unit 4: Priority Queues I [Link] (CSE) - I Sem

3. Remove or delete an element

The abstract data type specification for a max priority queue is given below.
The specification for a min priority queue is the same as ordinary queue except while deletion, find and
remove the element with minimum priority
ABSTRACT DAТА ТҮРE(ADT):
Abstract data type maxPriorityQueue
{
Instances: Finite collection of elements, each has a priority
Operations:
empty():return true iff the queue is empty
size() :return number of elements in the queue
top() :return element with maximum priority
del() :remove the element with largest priority from the queue
insert(x): insert the element x into the queue
}

Creating PriorityQueue
In order to create a priority queue, we must import the [Link] package. Once we import
the package, here is how we can create a priority queue in Java.

PriorityQueue<Integer> numbers = new PriorityQueue<>();

Here, we have created a priority queue without any arguments. In this case, the head of the priority
queue is the smallest element of the queue. And elements are removed in ascending order from the
queue.
However, we can customize the ordering of elements with the help of the Comparator interface.

Methods of PriorityQueue
The PriorityQueue class provides the implementation of all the methods present in the Queue interface.

Insert Elements to PriorityQueue

 add() - Inserts the specified element to the queue. If the queue is full, it throws an exception.
 offer() - Inserts the specified element to the queue. If the queue is full, it returns false.
Access PriorityQueue Elements
 To access elements from a priority queue, we can use the peek() method. This method returns the
head of the queue.
Remove PriorityQueue Elements
 remove() - removes the specified element from the queue
 poll() - returns and removes the head of the queue
For example,
import [Link];
class Main {
public static void main(String[] args) {
// Creating a priority queue

VLITS, Vadlamudi. Page 2

 Unit 4: Priority Queues I [Link] (CSE) - I Sem

PriorityQueue<Integer> numbers = new PriorityQueue<>();

// Using the add() method

[Link](4);
[Link](2);
[Link]("PriorityQueue: " + numbers);

// Using the offer() method

[Link](1);
[Link]("Updated PriorityQueue: " + numbers);

// Using the peek() method

int number = [Link]();
[Link]("Accessed Element: " + number);

// Using the remove() method

boolean result = [Link](2);
[Link]("Is the element 2 removed? " + result);

// Using the poll() method

int number = [Link]();
[Link]("Removed Element Using poll(): " + number);

}
}
Output

PriorityQueue: [2, 4]
Updated PriorityQueue: [1, 4, 2]
Accessed Element: 1
Is the element 2 removed? true
Removed Element Using poll(): 1

Here, we have created a priority queue named numbers. We have inserted 4 and 2 to the queue.
Although 4 is inserted before 2, the head of the queue is 2. It is because the head of the priority queue is
the smallest element of the queue.
We have then inserted 1 to the queue. The queue is now rearranged to store the smallest element 1 to the
head of the queue.

Iterating Over a PriorityQueue

To iterate over the elements of a priority queue, we can use the iterator() method. In order to use this
method, we must import the [Link] package. For example,
import [Link];
import [Link];

VLITS, Vadlamudi. Page 3

 Unit 4: Priority Queues I [Link] (CSE) - I Sem

class Main {
public static void main(String[] args) {

// Creating a priority queue

PriorityQueue<Integer> numbers = new PriorityQueue<>();
[Link](4);
[Link](2);
[Link](1);
[Link]("PriorityQueue using iterator(): ");

//Using the iterator() method

Iterator<Integer> iterate = [Link]();
while([Link]()) {
[Link]([Link]());
[Link](", ");
}
}
}
Output

PriorityQueue using iterator(): 1, 4, 2,

Other PriorityQueue Methods

Methods Descriptions
contains(element Searches the priority queue for the specified element. If the element is found,
) it returns true, if not it returns false.
size() Returns the length of the priority queue.
toArray() Converts a priority queue to an array and returns it.

Heap Data Structure:

Heap is a special case of balanced binary tree data structure where the root-node key is compared with
its children and arranged accordingly. If α has child node β then −

key(α) ≥ key(β)

As the value of parent is greater than that of child, this property generates Max Heap. Based on this
criteria, a heap can be of two types −

For Input → 35 33 42 10 14 19 27 44 26 31

Min-Heap − Where the value of the root node is less than or equal to either of its children.

VLITS, Vadlamudi. Page 4

 Unit 4: Priority Queues I [Link] (CSE) - I Sem

Max-Heap − Where the value of the root node is greater than or equal to either of its children.

Both trees are constructed using the same input and order of arrival.

Max Heap Construction Algorithm

The procedure to create Min Heap is similar but we go for min values instead of max values.

Algorithm: Max Heap by inserting one element at a time. At any point of time, heap must maintain
its property. While insertion, we also assume that we are inserting a node in an already heapified tree.

 Step 1 − Create a new node at the end of heap.

 Step 2 − Assign new value to the node.
 Step 3 − Compare the value of this child node with its parent.
 Step 4 − If value of parent is less than child, then swap them.
 Step 5 − Repeat step 3 & 4 until Heap property holds.

Note − In Min Heap construction algorithm, we expect the value of the parent node to be less than that
of the child node.

Ex: Max Heap construction

VLITS, Vadlamudi. Page 5

 Unit 4: Priority Queues I [Link] (CSE) - I Sem

VLITS, Vadlamudi. Page 6

 Unit 4: Priority Queues I [Link] (CSE) - I Sem

VLITS, Vadlamudi. Page 7

 Unit 4: Priority Queues I [Link] (CSE) - I Sem

Example
Following are the implementations of this operation in various programming languages −
// Java code for for Max Heap construction Algorithm
//Structure to represent a heap
public class MaxHeap {
private int[] heap; // To store heap elements
private int capacity; // Maximum capacity of the heap
private int size; // Current size of the heap
// To create a new heap
public MaxHeap(int capacity) {
[Link] = capacity;
[Link] = 0;
[Link] = new int[capacity];
}
private int parent(int i) {
return (i - 1) / 2;
}
private int leftChild(int i) {
return 2 * i + 1;
}
private int rightChild(int i) {
return 2 * i + 2;
}
private void swap(int i, int j) {
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
// Heapify a subtree rooted at index i
private void heapifyDown(int i) {
int largest = i;
int left = leftChild(i);
int right = rightChild(i);
// Check if the left child is larger than the root
if (left < size && heap[left] > heap[largest])
largest = left;
// Check if the right child is larger than the largest so far
if (right < size && heap[right] > heap[largest])
largest = right;
// If the largest is not the root, swap the root with the largest
if (largest != i) {
swap(i, largest);
heapifyDown(largest);
}

VLITS, Vadlamudi. Page 8

 Unit 4: Priority Queues I [Link] (CSE) - I Sem

}
private void heapifyUp(int i) {
while (i > 0 && heap[i] > heap[parent(i)]) {
int parent = parent(i);
swap(i, parent);
i = parent;
}
}
// Insert the new element at the end
public void insert(int value) {
if (size == capacity) {
[Link]("Heap is full. Cannot insert more elements.");
return;
}
heap[size] = value;
size++;
heapifyUp(size - 1);
}
// Function to extract the maximum element from the heap
public int extractMax() {
if (size == 0) {
[Link]("Heap is empty. Cannot extract maximum element.");
return -1;
}
// store th root element
int max = heap[0];
//Replace the root with the last elements
heap[0] = heap[size - 1];
size--;
heapifyDown(0);
return max;
}
//print the elements of the heap
public void printHeap() {
[Link]("Heap elements: ");
for (int i = 0; i < size; i++) {
[Link](heap[i] + " ");
}
[Link]();
}
public static void main(String[] args) {
MaxHeap heap = new MaxHeap(10);
[Link](35);
[Link](33);

VLITS, Vadlamudi. Page 9

 Unit 4: Priority Queues I [Link] (CSE) - I Sem

[Link](42);
[Link](10);
[Link](14);
[Link](19);
[Link](27);
[Link](44);
[Link](26);
[Link](31);
[Link]();
int max = [Link]();
[Link]("Maximum element: " + max);
}
}
Output
Heap elements: 44 42 35 33 31 19 27 10 26 14
Maximum element: 44

Max Heap Deletion Algorithm

Let us derive an algorithm to delete from max heap. Deletion in Max (or Min) Heap always happens at
the root to remove the Maximum (or minimum) value.

 Step 1 − Remove root node.

 Step 2 − Move the last element of last level to root.
 Step 3 − Compare the value of this child node with its parent.
 Step 4 − If value of parent is less than child, then swap them.
 Step 5 − Repeat step 3 & 4 until Heap property holds.

Example

VLITS, Vadlamudi. Page 10

 Unit 4: Priority Queues I [Link] (CSE) - I Sem

// Java code for for Max Heap Deletion Algorithm

// Structure to represent a heap
class Heap {

VLITS, Vadlamudi. Page 11

 Unit 4: Priority Queues I [Link] (CSE) - I Sem

private int[] array; // Array to store heap elements

private int capacity; // Maximum capacity of the heap
private int size; // Current size of the heap
// To create a new heap
public Heap(int capacity) {
[Link] = new int[capacity];
[Link] = capacity;
[Link] = 0;
}
// Swap two elements in the heap
private void swap(int a, int b) {
int temp = array[a];
array[a] = array[b];
array[b] = temp;
}
// Heapify a subtree rooted at index i
private void heapify(int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
// Check if the left child is larger than the root
if (left < size && array[left] > array[largest])
largest = left;
// Check if the right child is larger than the largest so far
if (right < size && array[right] > array[largest])
largest = right;
// If the largest is not the root, swap the root with the largest
if (largest != i) {
swap(i, largest);
heapify(largest);
}
}
// Insert a new element into the heap
public void insert(int value) {
if (size == capacity) {
[Link]("Heap is full. Cannot insert more elements.");
return;
}
// Insert the new element at the end
int i = size++;
array[i] = value;
// Fix the heap property if it is violated
while (i != 0 && array[(i - 1) / 2] < array[i]) {
swap(i, (i - 1) / 2);

VLITS, Vadlamudi. Page 12

 Unit 4: Priority Queues I [Link] (CSE) - I Sem

i = (i - 1) / 2;
}
}
// Delete the maximum element from the heap
public int deleteMax() {
if (size == 0) {
[Link]("Heap is empty. Cannot extract maximum element.");
return -1;
}
// Store the root element
int max = array[0];
// Replace the root with the last element
array[0] = array[size - 1];
size--;
// Heapify the root
heapify(0);
return max;
}
// Print the elements of the heap
public void printHeap() {
for (int i = 0; i < size; i++) {
[Link](array[i] + " ");
}
[Link]();
}
// Deallocate memory occupied by the heap
public void destroyHeap() {
array = null;
size = 0;
}
}
//Inserting the elements
public class Main {
public static void main(String[] args) {
Heap heap = new Heap(10);
[Link](35);
[Link](33);
[Link](42);
[Link](10);
[Link](14);
[Link](19);
[Link](27);
[Link](44);
[Link](26);

VLITS, Vadlamudi. Page 13

 Unit 4: Priority Queues I [Link] (CSE) - I Sem

[Link](31);
[Link]("Heap elements before deletion: ");
[Link]();
int max = [Link]();
[Link]("Maximum element: " + max);
//Printing the heap elements after deletion of max element
[Link]("Heap elements after deletion: ");
[Link]();
[Link]();
}
}
Output
Heap elements before deletion: 44 42 35 33 31 19 27 10 26 14
Maximum element: 44
Heap elements after deletion: 42 33 35 26 31 19 27 10 14

Binary Search Tree

A Binary Search Tree (BST) is a type of binary tree data structure in which each node contains a unique
key and satisfies a specific ordering property:
 All nodes in the left subtree of a node contain values strictly less than the node’s value.
 All nodes in the right subtree of a node contain values strictly greater than the node’s value.
 BST doesn’t contain any duplicate values.

Thus, BST divides all its sub-trees into two segments; the left sub-tree and the right sub-tree and can be
defined as −
left_subtree (keys) <= node (key) <= right_subtree (keys)

Binary Tree Representation

BST is a collection of nodes arranged in a way where they maintain BST properties. Each node has a
key and an associated value. While searching, the desired key is compared to the keys in BST and if
found, the associated value is retrieved.
Following is a pictorial representation of BST –

We observe that the root node key (27) has all less-valued keys on the left sub-tree and the higher
valued keys on the right sub-tree.
Basic Operations
Following are the basic operations of a Binary Search Tree −
 Search − Searches an element in a tree.
 Insert − Inserts an element in a tree.

VLITS, Vadlamudi. Page 14

 Unit 4: Priority Queues I [Link] (CSE) - I Sem

 Pre-order Traversal − Traverses a tree in a pre-order manner.

 In-order Traversal − Traverses a tree in an in-order manner.
 Post-order Traversal − Traverses a tree in a post-order manner.
 Deletion – Deletes an element from the tree
Defining a Node
Define a node that stores some data, and references to its left and right child nodes.
struct node {
int data;
struct node *leftChild;
struct node *rightChild;
};
Search Operation
Whenever an element is to be searched, start searching from the root node. Then if the data is less than
the key value, search for the element in the left subtree. Otherwise, search for the element in the right
subtree.
Algorithm
1. START
2. Check whether the tree is empty or not
3. If the tree is empty, search is not possible
4. Otherwise, first search the root of the tree.
5. If the key does not match with the value in the root, search its subtrees.
6. If the value of the key is less than the root value, search the left subtree
7. If the value of the key is greater than the root value, search the right subtree.
8. If the key is not found in the tree, return unsuccessful search.
9. END
Example
import [Link];
class BSTNode {
BSTNode left, right;
int data;
public BSTNode(int n) {
left = null;
right = null;
data = n;
}
}
public class BST {
static BSTNode root;
public BST() {
root = null;
}
private BSTNode insert(BSTNode node, int data) {
if(node == null)
node = new BSTNode(data);

VLITS, Vadlamudi. Page 15

 Unit 4: Priority Queues I [Link] (CSE) - I Sem

else {
if(data <= [Link])
[Link] = insert([Link], data);
else
[Link] = insert([Link], data);
}
return node;
}
private boolean search(BSTNode r, int val) {
boolean found = false;
while ((r != null) && !found) {
int rval = [Link];
if(val < rval)
r = [Link];
else if (val > rval)
r = [Link];
else {
found = true;
break;
}
found = search(r, val);
}
return found;
}
void printTree(BSTNode node, String prefix) {
if(node == null)
return;
printTree([Link] , " " + prefix);
[Link](prefix + "--" + [Link] + " ");
printTree([Link] , prefix);
}
public static void main(String args[]) {
Scanner sc = new Scanner([Link]);
BST bst = new BST();
root = [Link](root, 55);
root = [Link](root, 20);
root = [Link](root, 90);
root = [Link](root, 80);
root = [Link](root, 50);
root = [Link](root, 35);
root = [Link](root, 15);
root = [Link](root, 65);
[Link]("Insertion Done");
[Link]("\nBST:\n");

VLITS, Vadlamudi. Page 16

 Unit 4: Priority Queues I [Link] (CSE) - I Sem

[Link](root, "");
int ele = 80;
[Link]("\nElement to be searched: " + ele);
[Link]("\nElement found: " + [Link](root, 80));
}
}
Output
Insertion Done
BST:
--15 --20 --35 --50 --55 --65 --80 --90
Element to be searched: 80
Element found: true

VLITS, Vadlamudi. Page 17

 Unit 4: Priority Queues I [Link] (CSE) - I Sem

Insertion Operation
Whenever an element is to be inserted, first locate its proper location. Start searching from the root
node, then if the data is less than the key value, search for the empty location in the left subtree and
insert the data. Otherwise, search for the empty location in the right subtree and insert the data.
Algorithm
1. START
2. If the tree is empty, insert the first element as the root node of the tree. The following elements
are added as the leaf nodes.
3. If an element is less than the root value, it is added into the left subtree as a leaf node.
4. If an element is greater than the root value, it is added into the right subtree as a leaf node.
5. The final leaf nodes of the tree point to NULL values as their child nodes.
6. END
Example
import [Link];
class BSTNode {
BSTNode left, right;
int data;
public BSTNode(int n) {
left = null;
right = null;
data = n;
}
}
public class BST {
static BSTNode root;
public BST() {
root = null;
}
private BSTNode insert(BSTNode node, int data) {
if(node == null)
node = new BSTNode(data);
else {
if(data <= [Link])
[Link] = insert([Link], data);
else
[Link] = insert([Link], data);
}
return node;
}
void printTree(BSTNode node, String prefix) {
if(node == null)
return;
printTree([Link] , " " + prefix);
[Link](prefix + "--" + [Link]);

VLITS, Vadlamudi. Page 18

 Unit 4: Priority Queues I [Link] (CSE) - I Sem

printTree([Link] , prefix + " ");

}
public static void main(String args[]) {
Scanner sc = new Scanner([Link]);
BST bst = new BST();
root = [Link](root, 55);
root = [Link](root, 20);
root = [Link](root, 90);
root = [Link](root, 80);
root = [Link](root, 50);
root = [Link](root, 35);
root = [Link](root, 15);
root = [Link](root, 65);
[Link]("Insertion done\n");
[Link]("BST:\n");
[Link](root, " ");
}
}
Output
Insertion done
BST:
--15 --20 --35 --50 --55 --65 --80 --90

VLITS, Vadlamudi. Page 19

 Unit 4: Priority Queues I [Link] (CSE) - I Sem

Deletion in Binary Search Tree (BST)

Deleting a node in a BST means removing the target node while ensuring that the tree remains a valid
BST. Depending on the structure of the node to be deleted, there are three possible scenarios:

VLITS, Vadlamudi. Page 20

 Unit 4: Priority Queues I [Link] (CSE) - I Sem

Case 1: Node has No Children (Leaf Node)

If the target node is a leaf node, it can be directly removed from the tree since it has no child to
maintain.

Case 2: Node has One Child(Left or Right Child)

If the target node has only one child, we remove the node and connect its parent directly to its only
child. This way, the tree remains valid after deletion of target node.
Case 3: Node has Two Children
If the target node has two children, deletion is slightly more complex.
To maintain the BST property, we need to find a replacement node for the target. The replacement can
be either:
 The inorder successor — the smallest value in the right subtree, which is the next greater value
than the target node.
 The inorder predecessor — the largest value in the left subtree, which is the next smaller value
than the target node.
Once the replacement node is chosen, we replace the target node’s value with that node’s value, and
then delete the replacement node, which will now fall under Case 1 (no children) or Case 2 (one child).

VLITS, Vadlamudi. Page 21

 Unit 4: Priority Queues I [Link] (CSE) - I Sem

Inorder Traversal
The inorder traversal operation in a Binary Search Tree visits all its nodes in the following order −
Firstly, we traverse the left child of the root node/current node, if any.
Next, traverse the current node.
Lastly, traverse the right child of the current node, if any.
Algorithm
1. START
2. Traverse the left subtree, recursively
3. Then, traverse the root node
4. Traverse the right subtree, recursively.
5. END
Example

VLITS, Vadlamudi. Page 22

 Unit 4: Priority Queues I [Link] (CSE) - I Sem

void inorder_traversal(Node node) {

if(node != null) {
inorder_traversal([Link]);
[Link]([Link] + " ->");
inorder_traversal([Link]);
}
}

Preorder Traversal
The preorder traversal operation in a Binary Search Tree visits all its nodes. However, the root node in it
is first printed, followed by its left subtree and then its right subtree.
Algorithm
1. START
2. Traverse the root node first.
3. Then traverse the left subtree, recursively
4. Later, traverse the right subtree, recursively.
5. END
Example
void preorder_traversal(Node node) {
if(node != null) {
[Link]([Link] + " ->");
preorder_traversal([Link]);
preorder_traversal([Link]);
}
}
Postorder Traversal
Like the other traversals, postorder traversal also visits all the nodes in a Binary Search Tree and
displays them. However, the left subtree is printed first, followed by the right subtree and lastly, the root
node.
Algorithm
1. START
2. Traverse the left subtree, recursively
3. Traverse the right subtree, recursively.
4. Then, traverse the root node
5. END
Example
void postorder_traversal(Node node) {
if(node != null) {
postorder_traversal([Link]);
postorder_traversal([Link]);
[Link]([Link] + " ->");
}
}

VLITS, Vadlamudi. Page 23

 Unit 4: Priority Queues I [Link] (CSE) - I Sem

Implementation of Binary Search Tree:

import [Link];
class BSTNode {
BSTNode left, right;
int data;
public BSTNode(int n) {
left = null;
right = null;
data = n;
}
}
public class BST {
static BSTNode root;
public BST() {
root = null;
}
public boolean isEmpty() {
return root == null;
}
private BSTNode insert(BSTNode node, int data) {
if(node == null)
node = new BSTNode(data);
else {
if(data <= [Link])
[Link] = insert([Link], data);
else
[Link] = insert([Link], data);
}
return node;
}
public void delete(int k) {
if(isEmpty ())
[Link]("TREE EMPTY");
else if(search (k) == false)
[Link]("SORRY " + k + " IS NOT PRESENT");
else {
root=delete(root,k);
[Link](k + " DELETED FROM THE TREE");
}
}
public BSTNode delete(BSTNode root, int k) {
BSTNode p, p2, n;
if([Link] == k) {
BSTNode lt, rt;

VLITS, Vadlamudi. Page 24

 Unit 4: Priority Queues I [Link] (CSE) - I Sem

lt = [Link];
rt = [Link];
if(lt == null && rt == null) {
return null;
} else if(lt == null) {
p = rt;
return p;
} else if(rt == null) {
p = lt;
return p;
} else {
p2 = rt;
p = rt;
while([Link] != null)
p = [Link];
[Link] = lt;
return p2;
}
}
if (k < [Link]) {
n = delete([Link], k);
[Link] = n;
} else {
n = delete([Link], k);
[Link] = n;
}
return root;
}
public boolean search(int val) {
return search(root, val);
}
private boolean search(BSTNode r, int val) {
boolean found = false;
while ((r != null) && !found) {
int rval = [Link];
if(val < rval)
r = [Link];
else if (val > rval)
r = [Link];
else {
found = true;
break;
}
found = search(r, val);

VLITS, Vadlamudi. Page 25

 Unit 4: Priority Queues I [Link] (CSE) - I Sem

}
return found;
}
void printTree(BSTNode node, String prefix) {
if(node == null)
return;
printTree([Link] , " " + prefix);
[Link](prefix + "--" + [Link]);
printTree([Link] , prefix + " ");
}
public static void main(String args[]) {
Scanner sc = new Scanner([Link]);
BST bst = new BST();
root = [Link](root, 55);
root = [Link](root, 20);
root = [Link](root, 90);
root = [Link](root, 80);
root = [Link](root, 50);
root = [Link](root, 35);
root = [Link](root, 15);
root = [Link](root, 65);
[Link](root, " ");
[Link](55);
[Link]("Element found = " + [Link](80));
[Link]("Is Tree Empty? " + [Link]());
}
}

VLITS, Vadlamudi. Page 26

 Unit 4: Priority Queues I [Link] (CSE) - I Sem

VLITS, Vadlamudi. Page 27

 Unit 4: Priority Queues I [Link] (CSE) - I Sem

VLITS, Vadlamudi. Page 28

 Unit 4: Priority Queues I [Link] (CSE) - I Sem

VLITS, Vadlamudi. Page 29