lOMoARcPSD|39776382

Data structures road map part 2

Data structures and algorithms (Egypt Japan University Of Science & Technology)

Scan to open on Studocu

Studocu is not sponsored or endorsed by any college or university

Downloaded by mohmed azam (yousefazam120@gmail.com)
 lOMoARcPSD|39776382

Data Structures RoadMap All course Codes

version II after Midterm
prepared by: omar essam

Hello, World! kindly, review lecture 7 due to its importance.

Trees Data structures

First watch this video
https://www.youtube.com/watch?v=quMfajPvW24&list=PL1DUmTEdeA6JlommmGP5wicYLxX5PVCQt&index=12

complete the following videos

1-https://www.youtube.com/watchv=dqgZd8qvXoY&list=PL1DUmTEdeA6JlommmGP5wicYLxX5PVCQt&index=13

2-https://www.youtube.com/watch?v=tEVTakjxSQ&list=PL1DUmTEdeA6JlommmGP5wicYLxX5PVCQt&index=14

after watching the videos go on and read the following from Geeks for Geeks or you can read from here:
https://www.geeksforgeeks.org/introduction-to-tree-data-structure-and-algorithm-tutorials/

A tree data structure is a hierarchical structure that is used to represent and organize data in a way that is easy to navigate and
search. It is a collection of nodes that are connected by edges and has a hierarchical relationship between the nodes. The topmost
node of the tree is called the root, and the nodes below it are called the child nodes. Each node can have multiple child nodes, and
these child nodes can also have their own child nodes, forming a recursive structure.

Data Structures RoadMap All course Codes version II after Midterm 1

Downloaded by mohmed azam (yousefazam120@gmail.com)

 lOMoARcPSD|39776382

Recursive Definition:

A tree consists of a root, and zero or more subtrees T1, T2, … , Tk such that there is an edge from the
root of the tree to the root of each subtree.

Why Tree is considered a non-linear data structure?

The data in a tree are not stored in a sequential manner i.e, they are not stored linearly. Instead, they are arranged on multiple
levels or we can say it is a hierarchical structure. For this reason, the tree is considered to be a non-linear data structure.

Basic Terminologies In Tree Data Structure:

Parent Node: The node which is a predecessor of a node is called the parent node of that node. {B} is the parent node of {D,
E}.

Data Structures RoadMap All course Codes version II after Midterm 2

Downloaded by mohmed azam (yousefazam120@gmail.com)

 lOMoARcPSD|39776382

Child Node: The node which is the immediate successor of a node is called the child node of that node. Examples: {D, E} are
the child nodes of {B}.

Root Node: The topmost node of a tree or the node which does not have any parent node is called the root node. {A} is the root
node of the tree. A non-empty tree must contain exactly one root node and exactly one path from the root to all other nodes of
the tree.

Leaf Node or External Node: The nodes which do not have any child nodes are called leaf nodes. {K, L, M, N, O, P} are the
leaf nodes of the tree.

Ancestor of a Node: Any predecessor nodes on the path of the root to that node are called Ancestors of that node. {A,B} are
the ancestor nodes of the node {E}

Descendant: Any successor node on the path from the leaf node to that node. {E,I} are the descendants of the node {B}.

Sibling: Children of the same parent node are called siblings. {D,E} are called siblings.

Level of a node: The count of edges on the path from the root node to that node. The root node has level 0.

Internal node: A node with at least one child is called Internal Node.

Neighbour of a Node: Parent or child nodes of that node are called neighbors of that node.

Subtree: Any node of the tree along with its descendant.

Properties of a Tree:
Number of edges: An edge can be defined as the connection between two nodes. If a tree has N nodes then it will have (N-1)
edges. There is only one path from each node to any other node of the tree.

Depth of a node: The depth of a node is defined as the length of the path from the root to that node. Each edge adds 1 unit of
length to the path. So, it can also be defined as the number of edges in the path from the root of the tree to the node.

Height of a node: The height of a node can be defined as the length of the longest path from the node to a leaf node of the
tree.

Height of the Tree: The height of a tree is the length of the longest path from the root of the tree to a leaf node of the tree.

Degree of a Node: The total count of subtrees attached to that node is called the degree of the node. The degree of a leaf node
must be 0. The degree of a tree is the maximum degree of a node among all the nodes in the tree.

Some more properties are:

Traversing in a tree is done by depth first search and breadth first search algorithm.

It has no loop and no circuit

It has no self-loop

Its hierarchical model.

Types of Tree data structures

The different types of tree data structures are as follows:

1. General tree (source main book , Dr. Samir explains from it)

A general tree data structure has no restriction on the number of nodes. It means that a parent node can have any number of child
nodes.

Formal Tree Definition

Formally, we define tree T to be a set of nodes storing elements in a parent-child
relationship with the following properties:
• If T is nonempty, it has a special node, called the root of T, that has no parent.
• Each node v of T different from the root has a unique parent node w; every node with parent w is a child of w.

Data Structures RoadMap All course Codes version II after Midterm 3

Downloaded by mohmed azam (yousefazam120@gmail.com)

 lOMoARcPSD|39776382

Other Node Relationships

Two nodes that are children of the same parent are siblings. A node v is external
if v has no children. A node v is internal if it has one or more children. External
nodes are also known as leaves

Ordered Trees
A tree is ordered if there is a linear ordering defined for the children of each node;
that is, we can identify children of a node as being the first, second, third, and so
on. Such an ordering is determined by how the tree is to be used, and is usually indicated by drawing the tree with siblings arranged
from left to right, corresponding
to their linear relationship. Ordered trees typically indicate the linear order relationship existing between siblings by listing them in a
sequence or iterator in the
correct order.

Tree Functions
p.parent( ): Return the parent of p; an error occurs if p is the root.
p.children( ): Return a position list containing the children of node p.
p.isRoot( ): Return true if p is the root and false otherwise.
p.isExternal( ): Return true if p is external and false otherwise.

size( ): Return the number of nodes in the tree.

empty( ): Return true if the tree is empty and false otherwise.
root( ): Return a position for the tree’s root; an error occurs if the tree is empty.
positions( ): Return a position list of all the nodes of the tree.

Data Structures RoadMap All course Codes version II after Midterm 4

Downloaded by mohmed azam (yousefazam120@gmail.com)

 lOMoARcPSD|39776382

Operation Time Complexity

isRoot O(1)

isExternal O(1)

parent O(1)

children(p) O(cp)

size O(1)

empty O(1)

root O(1)

positions O(n)

Note:

"p" is a position in the tree.

"c" is the number of children of position "p".

"n" is the number of nodes in the tree.

Tree Traversal Algorithms

here are some important algorithms

finding the depth algorithm

Let p be a node of a tree T. The depth of p is the number of ancestors of p, excluding p itself. For example, in the tree of Figure 7.2,
the node storing International has depth 2. Note that this definition implies that the depth of the root of T is 0.
The depth of p’s node can also be recursively defined as follows:
• If p is the root, then the depth of p is 0
• Otherwise, the depth of p is one plus the depth of the parent of p

Data Structures RoadMap All course Codes version II after Midterm 5

Downloaded by mohmed azam (yousefazam120@gmail.com)

 lOMoARcPSD|39776382

Based on the above definition, the recursive algorithm depth(T, p) shown in Code Fragment 7.3, computes the depth of a node
referenced by position p of T by calling itself recursively on the parent of p, and adding 1 to the value returned.

int depth(const Tree& T, Position&p){

if((p.isRoot())
return 0; // root has depth 0
else
return 1 + depth(T, p.parent()); // 1 + (depth of parent)
}

Time complexity of this algorithm is O(dp) which is the same as O(n)

finding the height of the Tree algorithm

The height of a node p in a tree T is also defined recursively.

• If p is external, then the height of p is 0
• Otherwise, the height of p is one plus the maximum height of a child of p
The height of a tree T is the height of the root of T.

int height1(const Tree& T) {

int h = 0;
PositionList nodes = T.positions(); // list of all nodes
for (Iterator q = nodes.begin(); q != nodes.end(); ++q) {
if (q−>isExternal())
h = max(h, depth(T, *q)); // get max depth among leaves
}
return h;
}
//complexity O(n^2)

int height2(const Tree& T, const Position& p) {

if (p.isExternal()) return 0; // leaf has height 0
int h = 0;
PositionList ch = p.children(); // list of children
for (Iterator q = ch.begin(); q != ch.end(); ++q)
h = max(h, height2(T, *q));
return 1 + h; // 1 + max height of children
}
//complexity O(n)

2. Binary tree

General Node Syntax:

struct Node //or by using oop we can use class Node and proceed into our implementations
{
int data;
struct Node *left_child;
struct Node *right_child;
};

A node of a binary tree can have a maximum of two child nodes. In the given tree diagram, node B, D, and F are left children, while
E, C, and G are the right children.

#include<iostream>
using namespace std;

class Node {
public:
int data; // data value stored in the node
Node* right, * left; // pointers to the right and left child nodes
Node(int value) {
// constructor to initialize the node with the given value and set left and right child nodes to NULL.
data = value;
right = left = NULL;
}

Data Structures RoadMap All course Codes version II after Midterm 6

Downloaded by mohmed azam (yousefazam120@gmail.com)

 lOMoARcPSD|39776382

};

class BST {
public:
Node* root; // pointer to the root node of the binary search tree
BST() {
root = NULL; // constructor to initialize the root pointer to NULL
}

Node* Insert(Node* r, int item) {

// recursive function to insert a new node with the given value in the binary search tree rooted at r

if (r == NULL) { // if r is NULL, create a new node with the given value

Node* newnode = new Node(item);
r = newnode; // set r to point to the new node
}
else if (item < r->data) {
// if item is less than the data value of r, insert it in the left subtree of r
r->left = Insert(r->left, item);
}
else if (item > r->data) {
// if item is greater than the data value of r, insert it in the right subtree of r
r->right = Insert(r->right, item);
}

return r; // return the modified root pointer

}

void Insert(int item) {

// function to insert a new node with the given value in the binary search tree
root = Insert(root, item); // call the recursive function Insert() with the root pointer and the value to be inserted
}

void Preorder(Node* r) { // a recursive function to traverse the binary search tree in preorder (root left right)
if (r == NULL) return; // if r is NULL, return
cout << r->data << "\t"; // print the data value of the root node
Preorder(r->left); // traverse the left subtree in preorder
Preorder(r->right); // traverse the right subtree in preorder
}

void Inorder(Node* r) { // a recursive function to traverse the binary search tree in inorder (left root right)
if (r == NULL) return; // if r is NULL, return
Inorder(r->left); // traverse the left subtree in inorder
cout << r->data << "\t"; // print the data value of the root node
Inorder(r->right); // traverse the right subtree in inorder
}

void Postorder(Node* r) { // a recursive function to traverse the binary search tree in postorder (left right root)
if (r == NULL) return; // if r is NULL, return
Postorder(r->left); // traverse the left subtree in postorder
Postorder(r->right); // traverse the right subtree in postorder
cout << r->data << "\t"; // print the data value of the root node
}
Node* Search(Node* r, int key) {
if (r == NULL) return NULL;
else if (r->data == key)return r;
else if (key < r->data) return Search(r->left, key);
else return Search(r->right, key);
}

bool Search(int key) {

Node* result = Search(root, key);
if (result == NULL) return false;
else return true;
}

Node* Findmin(Node* r) {
if (r == NULL)
return NULL;
else if (r->left == NULL)
return r;
else
return Findmin(r->left);
}

Node* Findmax(Node* r) {
if (r == NULL)
return NULL;
else if (r->right == NULL)

Data Structures RoadMap All course Codes version II after Midterm 7

Downloaded by mohmed azam (yousefazam120@gmail.com)

 lOMoARcPSD|39776382

return r;
else
return Findmax(r->right);
}

// This method takes in a root node 'r' and an integer value 'key' that needs to be deleted from the BST.
Node* Delete(Node* r, int key) {

// If the root node is null, return null.

if (r == NULL)
return NULL;

// If the value of 'key' is less than the value of the current node's data, call 'Delete' function recursively on the left child.
if (key < r->data)
r->left = Delete(r->left, key);

// If the value of 'key' is greater than the value of the current node's data, call 'Delete' function recursively on the right child.
else if (key > r->data)
r->right = Delete(r->right, key);

// If the value of 'key' matches the value of the current node's data.
else {
// If the current node is a leaf node, delete it by setting it to null.
if (r->left == NULL && r->right == NULL) {
r = NULL;
}
// If the current node has only one child (at the left), replace it with the child node and delete the parent node.
else if (r->left != NULL && r->right == NULL) {
r->data = r->left->data;
delete r->left;
r->left = NULL;
}
// If the current node has only one child (at the right), replace it with the child node and delete the parent node.
else if (r->left == NULL && r->right != NULL) {
r->data = r->right->data;
delete r->right;
r->right = NULL;
}
// If the current node has two children, replace it with the maximum node in its left subtree and recursively delete the maximum node
else {
Node* max = Findmax(r->left);
r->data = max->data;
r->left = Delete(r->left, max->data);
}
}
// Return the root node of the modified BST.
return r;
}

};

int main() {
BST btree; // create an object of the BST class
int arr[9] = { 45,15,79,90,10,55,12,20,50 }; // an array of integers to be inserted in the binary search tree
for (int i = 0; i < 9; i++) {
btree.Insert(arr[i]); // insert each integer in the binary search tree
}

btree.Inorder(btree.root);
cout << "\n--------------------------------------------------------\n";
btree.Preorder(btree.root);
cout << "\n--------------------------------------------------------\n";
btree.Postorder(btree.root);
cout << "\n--------------------------------------------------------\n";
// Declare an integer variable 'key' to store the value that the user wants to search for.
int key;

// Ask the user to enter the item to search for.

cout << "Enter item to search for\n";

// Read the user input and store it in 'key'.

cin >> key;

// Call the 'Search' function of a binary search tree object 'btree' to check if 'key' is in the tree.
// If it is found, print "Item Found"; otherwise, print "Sorry, item not found".
if (btree.Search(key)) {
cout << "Item Found" << endl;
}
else {

Data Structures RoadMap All course Codes version II after Midterm 8

Downloaded by mohmed azam (yousefazam120@gmail.com)

 lOMoARcPSD|39776382

cout << "Sorry, item not found\n";

}

// Find the minimum element of the binary search tree by calling the 'Findmin' function of 'btree'.
// If the tree is empty (i.e., the root is null), print "No elements in the Tree";
// otherwise, print the minimum element's value.
cout << "Find minimum\n";
Node* min = btree.Findmin(btree.root);
if (min == 0) {
cout << "No elements in the Tree" << endl;
}
else {
cout << min->data << endl;
}

// Find the maximum element of the binary search tree by calling the 'Findmax' function of 'btree'.
// If the tree is empty (i.e., the root is null), print "No elements in the Tree";
// otherwise, print the maximum element's value.
cout << "Find maximum\n";
Node* max = btree.Findmax(btree.root);
if (max == 0) {
cout << "No elements in the Tree" << endl;
}
else {
cout << max->data << endl;
}

// Delete two items (12 and 15) from the binary search tree by calling the 'Delete' function of 'btree'.
// The 'Delete' function returns a pointer to the root of the modified tree.
Node* result = btree.Delete(btree.root, 12);
cout << "\nPreorder after delete 12\n";
// Print the elements of the modified tree in preorder traversal by calling the 'Preorder' function of 'btree'.
btree.Preorder(result);

result = btree.Delete(btree.root, 15);

cout << "\npreorder After Delete 15\n";
// Print the elements of the modified tree in preorder traversal by calling the 'Preorder' function of 'btree'.
btree.Preorder(result);

3. Balanced tree

If the height of the left sub-tree and the right sub-tree is equal or differs at most by 1, the tree is known as a balanced tree.

Priority queues
first we will summarize the ADT methods and terminologies

Applications require comparing and ranking objects based on parameters called "keys"

Keys are assigned to elements as specific attributes and can identify, rank, or weigh them

Keys may represent properties that an element did not originally possess

The key assigned to an element may not be unique and can be changed by the application

Keys can be of any type appropriate for a particular application

Keys can sometimes be complex properties that cannot be quantified with a single number

Keys can be extracted from the object itself or externally generated by the application.

Comparing trees with the total order:

A priority queue needs a comparison rule that defines a total order relation

The total order relation must satisfy the reflexive, antisymmetric, and transitive properties

A priority queue is a container of elements, each associated with a key that determines the priority

The fundamental functions of a priority queue are insert, min, and removeMin

Data Structures RoadMap All course Codes version II after Midterm 9

Downloaded by mohmed azam (yousefazam120@gmail.com)

 lOMoARcPSD|39776382

The removeMin function removes the same element returned by min, which is the element with the smallest associated key
value

The example given is a priority queue of standby passengers for a fully booked flight, where the priority of each passenger is
determined by fare paid, frequent-flyer status, and time of insertion

Comparators
The issue of how to compare elements in a priority queue is important and has different solutions.

Implementing a different priority queue for each element type and comparison method is a direct but not very general solution.

A better solution is to design the priority queue as a templated class, where the element type is specified as an abstract
template argument (E) and each concrete class provides a means for comparing two objects of type E.

This could be done through a "comp" function or overloading the C++ comparison operator "<".

A concrete example is provided with a class Point2D that defines a two-dimensional point and a lexicographical less-than
operator based on the relative values of x and y coordinates.

bool operator<(const Point2D& p, const Point2D& q) {

if (p.getX() == q.getX())
return p.getY() < q.getY();
else
return p.getX() < q.getX();
}

Data Structures RoadMap All course Codes version II after Midterm 10

Downloaded by mohmed azam (yousefazam120@gmail.com)

 lOMoARcPSD|39776382

This approach of overloading the relational operators is general enough for many situations, but it relies on the assumption that
objects of the same type are always compared in the same way. There are situations, however, where it is desirable to apply
different comparisons to objects of the same type. Consider the following examples.

Example 8.2: There are at least two ways of comparing the C++ character strings, "4" and "12". In the lexicographic ordering, which
is an extension of the alphabetic ordering to character strings, we have "4" > "12". But if we interpret these strings as integers, then
"4" < "12".

1. The composition method involves defining each entry of a priority queue as a pair (e,k), where e is the element and k is the key
that defines the priority ordering. Each key object defines its own comparison function. This approach is very general and is
studied in Chapter 9.

2. The approach used is based on defining a special object called a comparator, whose job is to provide a definition of the
comparison function between any two elements. A comparator for element type E can be implemented as a class that defines a
single function whose job is to compare two objects of type E. It is possible to derive all the other relational operators by
combining less-than comparisons with other boolean operators.

Defining and Using Comparator Objects

special objects that provide a definition of the comparison function between any two elements. It presents an example of how to
implement comparators in C++ using a class structure called Point2D, and provides two comparators, LeftRight and BottomTop, that
implement left-to-right and bottom-to-top ordering by comparing the x and y coordinates of the points, respectively. The article also
explains how to use these comparators by declaring objects of the comparator classes and invoking the "()" operator with the two
points to be compared.

class LeftRight { // a left-right comparator

public:
bool operator()(const Point2D& p, const Point2D& q) const
{ return p.getX() < q.getX(); }
};

class BottomTop { // a bottom-top comparator

public:
bool operator()(const Point2D& p, const Point2D& q) const
{ return p.getY() < q.getY(); }
};

The code fragment 8.2 shows a generic function printSmaller that takes two arguments and prints the smaller of the two. The
function is templated by the element type E and the comparator type C, where C implements a less-than function for two objects of
type E. The function takes three arguments, the two elements to be compared, p and q, and an instance of a comparator, isLess ,
for these elements. It then uses the comparator to determine which element is smaller and prints that value.

template <typename E, typename C> // element type and comparator

void printSmaller(const E& p, const E& q, const C& isLess) {
cout << (isLess(p, q) ? p : q) << endl; // print the smaller of p and q
}

Point2D p(1.3, 5.7), q(2.5, 0.6); // two points

LeftRight leftRight; // a left-right comparator
BottomTop bottomTop; // a bottom-top comparator
printSmaller(p, q, leftRight); // outputs: (1.3, 5.7)
printSmaller(p, q, bottomTop); // outputs: (2.5, 0.6)
// Code Fragment 8.3: The use of two comparators to implement different
// behaviorsfrom the function printSmaller.

Data Structures RoadMap All course Codes version II after Midterm 11

Downloaded by mohmed azam (yousefazam120@gmail.com)

 lOMoARcPSD|39776382

The comparator approach is a bit less general than the composition method, because the comparator bases its decisions on the
contents of the elements themselves. In the composition method, the key may contain information that is not part of the element
object. The comparator approach has the advantage of being simpler, since we can insert elements directly into our priority queue
without creating element-key pairs. Furthermore, in Exercise R-8.4 we show that there is no real loss of generality in using
comparators

8.1.3 The Priority Queue ADT

Abstract Data Type

Having described the priority queue abstract data type at an intuitive level, we now describe it in more detail. As an ADT, a priority
queue P supports the following functions:

size(): Return the number of elements in P. empty(): Return true if P is empty and false otherwise. insert(e): Insert a new element
e into P.

min(): Return a reference to an element of P with the smallest associated key value (but do not remove it); an error condition
occurs if the priority queue is empty.

removeMin(): Remove from P the element referenced by min(); an error condition occurs if the priority queue is empty.

As mentioned above, the primary functions of the priority queue ADT are the insert, min, and removeMin operations. The other
functions, size and empty, are generic collection operations. Note that we allow a priority queue to have multiple entries with the
same key.

Operation Output Priority Queue

insert(5) – {5}

insert(9) – {5,9}

insert(2) – {2,5,9}

Data Structures RoadMap All course Codes version II after Midterm 12

Downloaded by mohmed azam (yousefazam120@gmail.com)

 lOMoARcPSD|39776382

insert(7) – {2,5,7,9}

min() [2] {2,5,7,9}

removeMin() – {5,7,9}

size() 3 {5,7,9}

min() [5] {5,7,9}

removeMin() – {7,9}

removeMin() – {9}

removeMin() – {}

empty() true {}

removeMin() “error” {}

8.1.4 A C++ Priority Queue Interface

Before discussing specific implementations of the priority queue, we first define an informal C++ interface for a priority queue in
Code Fragment 8.4. It is not a complete C++ class, just a declaration of the public functions.

template <typename E, typename C> // element and comparator

class PriorityQueue { // priority-queue interface
public:
int size() const; // number of elements
bool isEmpty() const; // is the queue empty?
void insert(const E& e); // insert element
const E& min() const throw(QueueEmpty); // minimum element
void removeMin() throw(QueueEmpty); // remove minimum
};

Code Fragment 8.4: An informal PriorityQueue interface (not a complete class)

Although the comparator type C is included as a template argument, it does not appear in the public interface. Of course, its value is
relevant to any concrete implementation

The function min returns a constant reference to the element in the queue, meaning that its value can be read but not modified. The
member functions size , empty , and min are all declared as constant. An error is thrown if the functions min or removeMin are called
on an empty priority queue, which is signaled by an exception of type QueueEmpty .

8.1.5 Sorting with a Priority Queue

Another important application of a priority queue is sorting, where we are given a collection L of n elements that can be compared
according to a total order relation, and we want to rearrange them in increasing order (or at least in nondecreasing order if there are
ties). The algorithm for sorting L with a priority queue Q, called PriorityQueueSort, is quite simple and consists of the following two
phases:

1. In the first phase, we put the elements of L into an initially empty priority queue P through a series of n insert operations, one
for each element.

2. In the second phase, we extract the elements from P in nondecreasing order by means of a series of n combinations of min
and removeMin operations, putting them back into L in order.

Pseudo-code for this algorithm is given in Code Fragment 8.5. It assumes that L is given as an STL list, but the code can be
adapted to other containers.

Algorithm PriorityQueueSort(L,P):
Input: An STL list L of n elements and a priority queue, P,
that compareselements using a total order relation
Output: The sorted list L

Data Structures RoadMap All course Codes version II after Midterm 13

Downloaded by mohmed azam (yousefazam120@gmail.com)

 lOMoARcPSD|39776382

while !L.empty() do
e ← L.front
L.pop front() {remove an element e from the list}
P.insert(e) {. . . and it to the priority queue}
while !P.empty() do
e ← P.min()P.removeMin() {remove the smallest element e from the queue}
L.push back(e) {. . . and append it to the back of L}

The algorithm works for any priority queue P regardless of its implementation.

The running time of the algorithm depends on the running times of operations insert, min, and removeMin, which depend on
how P is implemented.

PriorityQueueSort is considered more a sorting "scheme" than a sorting "algorithm" because it doesn't specify how P is
implemented.

The PriorityQueueSort scheme is the paradigm of several popular sorting algorithms, including selection-sort, insertion-sort, and
heap-sort, which are discussed in the chapter.

8.1.6 The STL priority queue Class

first watch this videos
https://www.youtube.com/watch?v=0zr0JqSw7ic&pp=ygUOcHJpb3JpdHkgcXVldWU%3D

The C++ Standard Template Library (STL) provides an implementation of a priority queue called priority_queue.

The priority_queue is a container in the STL, and its definition file is called "queue."

The priority_queue class is templated with three parameters: the base type of the elements, the underlying STL container, and
the comparator object.

The second parameter (the underlying container) defaults to the STL vector, and the third parameter (the comparator) defaults
to using the standard C++ less-than operator.

The STL priority queue uses comparators in the same way as defined in Section 8.1.2, where a comparator is a class that
overrides the "()" operator to define a boolean function that implements the less-than operator.

Two STL priority queues are defined in the code fragment, one storing integers and the other storing two-dimensional points
under the left-to-right ordering.

#include <queue>
using namespace std; // make std accessible
priority_queue<int> p1; // a priority queue of integers
// a priority queue of
// points with left-to-right order
priority_queue<Point2D, vector<Point2D>, LeftRight> p2;

here is a complete subprogram

#include<iostream>
#include<queue>

using namespace std;

int main() {
priority_queue<int,vector<int>,less<int>>pq;
pq.push(10);
pq.push(80);
pq.push(60);
pq.push(50);
pq.push(90);

Data Structures RoadMap All course Codes version II after Midterm 14

Downloaded by mohmed azam (yousefazam120@gmail.com)

 lOMoARcPSD|39776382

pq.push(100);

while(!pq.empty()){
cout << pq.top() << endl;
pq.pop();
}
}

size(): Return the number of elements in the priority queue.

empty(): Return true if the priority queue is empty and false otherwise.

push(e): Insert e in the priority queue.

top(): Return a constant reference to the largest element of the priority queue.

pop(): Remove the element at the top of the priority queue.

Other than the differences in function names, the most significant difference between our interface and the STL priority queue is that
the functions top and pop access the largest item in the queue according to priority order, rather than the smallest. An example of
the usage of the STL priority queue is shown in Code Fragment 8.6.

priority queue<Point2D, vector<Point2D>, LeftRight> p2;

p2.push( Point2D(8.5, 4.6) ); // add three points to p2
p2.push( Point2D(1.3, 5.7) );p2.push( Point2D(2.5, 0.6) );
cout << p2.top() << endl; p2.pop(); // output: (8.5, 4.6)
cout << p2.top() << endl; p2.pop(); // output: (2.5, 0.6)
cout << p2.top() << endl; p2.pop(); // output: (1.3, 5.7)

8.2 Implementing a Priority Queue with a List

Implementation with an Unsorted List

Priority queue P can be implemented using an unsorted doubly linked list L.

Insertion of an element e into P can be done in O(1) time by adding e to the end of L using L.push back(e).

Since the list is unsorted, both min and removeMin operations require searching all elements of the list, taking O(n) time each,
where n is the number of elements in P.

Size and empty functions can be implemented by returning the corresponding functions of list L.

Using an unsorted list for P results in constant-time insertion but linear-time search and removal.

Implementation with a Sorted List

Priority queue is implemented using a list sorted by non-decreasing key values.

Function min is implemented by accessing the first element of the list, and removeMin is implemented by removing the first
element of the list.

Insert function requires scanning through the list to find the appropriate position, making it take O(n) time.

If the list is implemented as a doubly linked list, then min and removeMin operations take O(1) time.

In summary, a sorted list implementation allows for fast queries and deletions, but slow insertions.

Operation Unsorted List Sorted List

size, empty O(1) O(1)

insert O(1) O(n)

min, removeMin O(n) O(1)

We assume that the list is implemented by a doubly linked list. The space requirement is O(n)

Data Structures RoadMap All course Codes version II after Midterm 15

Downloaded by mohmed azam (yousefazam120@gmail.com)

 lOMoARcPSD|39776382

8.2.1 A C++ Priority Queue Implementation using a List

#include<iostream>
#include<queue>
#include<list>

template <typename E, typename C>

class ListPriorityQueue {
public:
int size() const; // number of elements
bool empty() const; // is the queue empty?
void insert(const E& e); // insert element
const E& min() const; // minimum element
void removeMin(); // remove minimum
private:
std::list<E> L; // priority queue contents
C isLess; // less-than comparator
};

template <typename E, typename C> // number of elements

int ListPriorityQueue<E, C>::size() const
{
return L.size();
}
template <typename E, typename C> // is the queue empty?
bool ListPriorityQueue<E, C>::empty() const
{
return L.empty();
}

template <typename E, typename C> // insert element

void ListPriorityQueue<E, C>::insert(const E& e) {
typename std::list<E>::iterator p;
p = L.begin();
while (p != L.end() && !isLess(e, *p)) ++p; // find larger element
L.insert(p, e); // insert e before p
}

template <typename E, typename C> // minimum element

const E& ListPriorityQueue<E, C>::min() const
{
return L.front();
} // minimum is at the front
template <typename E, typename C> // remove minimum
void ListPriorityQueue<E, C>::removeMin()
{
L.pop front();
}

Note: this code will be explained later with complete implementation

8.2.2 Selection-Sort and Insertion-Sort

Recall the PriorityQueueSort scheme introduced in Section 8.1.5. We are given an unsorted list L containing n elements, which we
sort using a priority queue P in two phases. In the first phase, we insert all the elements, and in the second phase, we repeatedly
remove elements using the min and removeMin operations.

Selection-Sort
The priority queue implementation using an unsorted list has a time complexity of O(n) for the first phase of PriorityQueueSort
since each element can be inserted in constant time.

In the second phase, the time complexity of each min and removeMin operation is proportional to the number of elements
currently in the unsorted list.

Data Structures RoadMap All course Codes version II after Midterm 16

Downloaded by mohmed azam (yousefazam120@gmail.com)

 lOMoARcPSD|39776382

The bottleneck in this implementation is the repeated selection of the minimum element from an unsorted list in the second
phase.

The algorithm implemented using an unsorted list for the priority queue is known as selection-sort.

As noted above, the bottleneck is the second phase, where we repeatedly remove an element with smallest key from the priority
queue P. The size of P starts at n and decreases to 0 with each removeMin. Thus, the first removeMin operation takes time O(n),
the second one takes time O(n-1), and so on. Therefore, the total time needed for the second phase is

Insertion-sort
Implementing priority queue P using a sorted list improves the second phase's running time to O(n) because min and
removeMin operations take O(1) time.

However, the first phase now becomes the bottleneck because each insert operation takes time proportional to the size of P in
the worst case.

This sorting algorithm is called insertion-sort because the bottleneck involves the repeated "insertion" of a new element at the
appropriate position in a sorted list.

Data Structures RoadMap All course Codes version II after Midterm 17

Downloaded by mohmed azam (yousefazam120@gmail.com)

 lOMoARcPSD|39776382

We can improve the performance of insertion-sort by changing our definition to insert elements from the end of the priority
queue sequence in the first phase.

This would make the worst-case running time of the first phase O(n^2), but the best-case running time O(n) for a pre-sorted
input list.

In this modified insertion-sort, the running time is O(n+I), where I is the number of inversions in the input list.

Inversions refer to pairs of elements in the input list that start out in the wrong relative order.

Thus, insertion-sort performs well on nearly sorted or partially sorted lists with few inversions, but poorly on highly unsorted lists
with many inversions.

Heaps
There are two implementations of the PriorityQueueSort scheme: selection-sort and insertion-sort.

Data Structures RoadMap All course Codes version II after Midterm 18

Downloaded by mohmed azam (yousefazam120@gmail.com)

 lOMoARcPSD|39776382

Selection-sort has a fast first phase but slow second phase, while insertion-sort has a slow first phase but a fast second phase.

Balancing the running times of the two phases could speed up the overall running time for sorting.

An efficient realization of a priority queue uses a heap data structure, which allows both insertions and removals in logarithmic
time.

Heaps store elements and keys in a binary tree instead of a list, which is what improves the running time.

The Heap Data Structure

A heap (see Figure 8.3) is a binary tree T that stores a collection of elements with their associated keys at its nodes and that
satisfies two additional properties: a relational property, defined in terms of the way keys are stored in T, and a structural property,
defined in terms of the nodes of T itself. We assume that a total order relation on the keys is given, for example, by a comparator.

The relational property of T, defined in terms of the way keys are stored, is the following:

Heap-Order Property: In a heap T, for every node v other than the root, the key associated with v is greater than or equal to the key
associated with v’s parent.

The heap data structure stores elements and keys in a binary tree.

The heap-order property states that the keys encountered on a path from the root to an external node of the binary tree are in
nondecreasing order.

The minimum key is always stored at the root of the binary tree.

The name "heap" comes from the fact that the most important key is informally said to be "at the top of the heap."

The heap data structure defined here is not related to the memory heap used in programming languages like C++.

The smallest key is conventionally stored at the top of a heap, but it is arbitrary.

A comparator is used to implement the less-than operator between two keys.

If the comparator were defined to indicate the opposite of the standard total order relation between keys, the root of the heap
would store the largest key.

This versatility is achieved through the use of the comparator pattern.

Data Structures RoadMap All course Codes version II after Midterm 19

Downloaded by mohmed azam (yousefazam120@gmail.com)

 lOMoARcPSD|39776382

The "minimum" key with a "reverse" comparator is actually the largest.

Therefore, without loss of generality, we always assume that we are interested in the minimum key, which is always at the root
of the heap.

For efficiency, the heap T must have as small a height as possible

The heap T must be complete in order to enforce this structural property

Level i of a binary tree T is the set of nodes of T that have depth i

Given nodes v and w on the same level of T, we say that v is to the left of w if v is encountered before w in an inorder traversal
of T

Complete Binary Tree Property: A heap T with height h is a complete binary tree, that is, levels 0,1,2,... ,h-1 of T have the maximum
number of nodes possible (namely, level i has 2i nodes, for 0 ≤ i ≤ h - 1) and the nodes at level h fill this level from left to right

The Height of a Heap

h = [ log n ] where n is the number of entries

Data Structures RoadMap All course Codes version II after Midterm 20

Downloaded by mohmed azam (yousefazam120@gmail.com)

 lOMoARcPSD|39776382

Implementing a Priority Queue with a Heap

Our heap-based representation for a priority queue P consists of the following:

heap: A complete binary tree T whose nodes store the elements of the queue and whose keys satisfy the heap-order property. We
assume the binary tree T is implemented using a vector, as described in Section 8.3.2. For each node v of T, we denote the
associated key by k(v).

comp: A comparator that defines the total order relation among the keys.

Data Structures RoadMap All course Codes version II after Midterm 21

Downloaded by mohmed azam (yousefazam120@gmail.com)

 lOMoARcPSD|39776382

insert

insert operation on a priority queue implemented with a heap T:

1. Add a new node z to T using the operation add and store the new element e in this node, making it the last node of T.

2. Compare the key k(z) with the key k(u) stored at the parent u of z. If k(z) ≥ k(u), the heap-order property is satisfied and the
algorithm terminates.

3. If k(z) < k(u), swap the entries stored at z and u. This causes the new entry (k, e) to move up one level.

4. Repeat step 2 and 3 until the heap-order property is satisfied.

5. The upward movement of the newly inserted entry by means of swaps is conventionally called up-heap bubbling.

6. In the worst case, up-heap bubbling causes the new entry to move all the way up to the root of heap T. Thus, in the worst
case, the number of swaps performed in the execution of function insert is equal to the height of T, which is ⌊logn⌋ by
Proposition 8.5.

Data Structures RoadMap All course Codes version II after Midterm 22

Downloaded by mohmed azam (yousefazam120@gmail.com)

 lOMoARcPSD|39776382

The upward movement of the newly inserted entry by means of swaps is conventionally called up-heap bubbling. A swap either
resolves the violation of the heap-order property or propagates it one level up in the heap. In the worst case, upheap bubbling

Data Structures RoadMap All course Codes version II after Midterm 23

Downloaded by mohmed azam (yousefazam120@gmail.com)

 lOMoARcPSD|39776382

causes the new entry to move all the way up to the root of heap T. (See Figure 8.7.) Thus, in the worst case, the number of swaps
performed in the execution of function insert is equal to the height of T, that is, it is log n by Proposition 8.5.

Removal

The algorithm for function removeMin using heap T is as follows:

1. If the heap T is empty, then there is no minimum element to remove and the algorithm terminates.

2. Store the element stored in the root node r in a variable minElem .

3. If the root node r is the only node in the heap T , delete it and the algorithm terminates.

4. Otherwise, move the last node w of the heap to the root position r and delete the node w . (See Figure 8.8(a) and (b).)

5. Compare the key k(u) stored at the new root u with the keys k(v) stored at its children v . If k(u) is larger than both k(v1)

and k(v2) , the heap-order property is satisfied and the algorithm terminates.

6. Otherwise, swap the entry stored at node u with the entry stored at the child node v with the smallest key. (See Figure 8.8(c)
and (d).)

7. Continue swapping and comparing up the heap T until the heap-order property is restored. (See Figure 8.8(e) and (f).)

8. Return the stored minimum element minElem .

Down-heap bubbling after a removal from a priority queue implemented with a heap:

1. Check if the heap T has only one node, the root. If yes, the heap-order property is trivially satisfied, and the algorithm
terminates.

2. If the root r has no right child, let s be the left child of r. Otherwise (if r has both children), let s be a child of r with the smaller key.

3. Check if k(r) ≤ k(s). If yes, the heap-order property is satisfied, and the algorithm terminates.

4. If k(r) > k(s), swap the entries stored at r and s to locally restore the heap-order property for node r and its children (but it may
still be violated at s).

5. Continue swapping down the heap T until no violation of the heap-order property occurs, propagating the violation one level
down the heap. This process is called down-heap bubbling.

6. In the worst case, an entry moves all the way down to the bottom level, and the number of swaps performed in the execution of
function removeMin is equal to the height of heap T, which is ⌊logn⌋.

Data Structures RoadMap All course Codes version II after Midterm 24

Downloaded by mohmed azam (yousefazam120@gmail.com)

 lOMoARcPSD|39776382

vector based heap implementation

https://www.youtube.com/watch?v=REOsj0nYWKE

watch this video it will explain this slide

Data Structures RoadMap All course Codes version II after Midterm 25

Downloaded by mohmed azam (yousefazam120@gmail.com)

 lOMoARcPSD|39776382

Hash Tables, Maps, and Skip Lists

Maps

Figure 9.1: A conceptual illustration of the map ADT. Keys (labels) are assigned to values (folders) by a user. The resulting entries
(labeled folders) are inserted into the map (file cabinet). The keys can be used later to retrieve or remove values.

A map stores key-value pairs (k,v), where k is the key and v is its corresponding value.

The map ADT requires each key to be unique, creating a mapping of keys to values.

Both keys and values can be of any object type.

The key is used as a unique identifier assigned by an application or user to an associated value object.

Maps are appropriate in situations where each key serves as a unique index address for its value.

Maps are sometimes referred to as associative stores or associative containers.

The composition pattern is a general object-oriented design pattern that defines a single object composed of other objects.

An entry in a map is an example of the composition pattern, combining a key and value into a single object.

Data Structures RoadMap All course Codes version II after Midterm 26

Downloaded by mohmed azam (yousefazam120@gmail.com)

 lOMoARcPSD|39776382

To implement this, we define a class that stores two objects and provides functions to access and update them.

Code Fragment 9.1 presents an implementation of an Entry class that is templated based on the key and value types.

The Entry class provides member functions to access and update the key and value members.

template <typename K, typename V>

class Entry { // a (key, value) pair
public: // public functions
Entry(const K& k = K(), const V& v = V()) : key(k), value(v) { } // constructor
const K& key() const {
return key;
} // get key
const V& value() const {
return value;
} // get value
void setKey(const K& k) {
key = k;
} // set key
void setValue(const V& v) {
value = v;
} // set value
private: // private data
K key; // key
V value; // value
};

Map ADTs
A map is a collection of key-value entries, with each value associated with a distinct key.

A special pointer object, called a position, allows us to reference entries of the map.

We define a more general object called an iterator, which can reference entries and navigate around the map.

Given a map iterator p, the associated entry may be accessed by dereferencing the iterator as *p.

The individual key and value can be accessed using p->key() and p->value(), respectively.

The increment operator is overloaded to advance an iterator to the next entry.

We can enumerate all the entries of a map by initializing an iterator to M.begin() and then repeatedly incrementing it until it is
equal to M.end().

A special sentinel iterator called end indicates that an object is not present in the map. By convention, it refers to an imaginary
element beyond the last element of the map.

Function Description

size() Return the number of entries in M.

empty() Return true if M is empty and false otherwise.

If M contains an entry e = (k,v), with key equal to k, then return an iterator p referring to this
find(k)
entry, and otherwise return the special iterator end.

If M does not have an entry with key equal to k, then add entry (k,v) to M, and otherwise, replace
put(k,v)
the value field of this entry with v; return an iterator to the inserted/modified entry.

erase(k) Remove from M the entry with key equal to k; an error condition occurs if M has no such entry.

Remove from M the entry referenced by iterator p; an error condition occurs if p points to the end
erase(p)
sentinel.

begin() Return an iterator to the first entry of M.

end() Return an iterator to a position just beyond the end of M.

Two means of removing entries from a map: given a key or given an iterator.

Key-based operation should only be used when it is known that the key is present in the map, otherwise, check for the key first
using "M.find(k)" and apply "M.erase(p)" if found.

Iterator-based removal operation is more efficient since it doesn't need to repeat the search for the key.

Data Structures RoadMap All course Codes version II after Midterm 27

Downloaded by mohmed azam (yousefazam120@gmail.com)

 lOMoARcPSD|39776382

The "put" operation can either insert an entry or modify an existing one. It is designed this way to ensure that keys are unique.

An iterator remains associated with an entry even if its value is changed.

Example 9.1 shows the effect of a series of operations on an initially empty map storing entries with integer keys and single-
character values. The entries of the map are not listed in any particular order.

A C++ Map Interface

Before discussing specific implementations of the map ADT, we first define a C++ interface for a map in Code Fragment 9.2. It is not
a complete C++ class, just a declaration of the public functions. The interface is templated by two types, the key type K, and the
value type V.

The Map interface defines two types: Entry and Iterator.

Entry and Iterator provide types for entry and iterator objects, respectively.

The iterator object is similar to the STL iterator and supports * operator, unary increment and decrement operators, and
comparison using ==.

A const iterator type is not provided in the interface.

The interface includes the functions described earlier for map operations.

If the erase(k) function is called with a key that is not in the map, an exception of type NonexistentElement is thrown.

Data Structures RoadMap All course Codes version II after Midterm 28

Downloaded by mohmed azam (yousefazam120@gmail.com)

 lOMoARcPSD|39776382

The STL map Class

The C++ Standard Template Library (STL) provides an implementation of a map called map .

map is a container and supports access by iterators.

To declare an object of type map , you need to include the definition file called "map", and it is part of the std namespace.

map is templated with two arguments, the key type and the value type. An iterator type is provided for referencing individual

entries and enumerating multiple entries.

The map iterator type is map<K,E>::iterator , and the (k,v) entries are stored in a composite object called pair.

Each map object defines two special iterators through the functions begin and end . A map iterator is bidirectional and can be
moved forwards and backwards using the increment and decrement operators.

The principal member functions of the STL map include insert , erase , find , clear , empty , and size .

Function Description

size() Return the number of elements in the map.

empty() Return true if the map is empty and false otherwise.

find(k) Find the entry with key k and return an iterator to it; if no such key exists return end.

operator[k] Produce a reference to the value of key k; if no such key exists, create a new entry for key k.

insert(pair(k,v)) Insert pair (k,v), returning an iterator to its position.

erase(k) Remove the element with key k.

erase(p) Remove the element referenced by iterator p.

begin() Return an iterator to the beginning of the map.

end() Return an iterator just past the end of the map.

The map ADT is similar to the functions provided by the STL map.

The STL map's insert function takes a composite object of type pair, with its first and second elements being the key and value.

Data Structures RoadMap All course Codes version II after Midterm 29

Downloaded by mohmed azam (yousefazam120@gmail.com)

 lOMoARcPSD|39776382

The subscript operator ("[]") in the STL map is used for convenient search, insert, and modify operations. It inserts the pair (k,v)
if k is not present or modifies the value if it is.

The value of M[k] can be read by performing find(k) and accessing the value part of the resulting iterator.

The use of the STL map is demonstrated in Code Fragment 9.3.

map<string, int> myMap; // a (string,int) map

map<string, int>::iterator p; // an iterator to the map
myMap.insert(pair<string, int>("Rob", 28)); // insert (“Rob”,28)
myMap["Joe"] = 38; // insert(“Joe”,38)
myMap["Joe"] = 50; // change to (“Joe”,50)
myMap["Sue"] = 75; // insert(“Sue”,75)
p = myMap.find("Joe"); // *p = (“Joe”,50)
myMap.erase(p); // remove (“Joe”,50)
myMap.erase("Sue"); // remove (“Sue”,75)
p = myMap.find("Joe");
if (p == myMap.end()) cout << "nonexistent\n"; // outputs: “nonexistent”
for (p = myMap.begin(); p != myMap.end(); ++p) { // print all entries
cout << "(" << p−>first << "," << p−>second << ")\n";
}

As with the other STL containers we have seen, the STL does not check for errors. It is up to the programmer to be sure that no
illegal operations are performed.

A Simple List-Based Map Implementation

A map can be implemented using a doubly linked list.

The list stores the n entries of the map.

The find(k), put(k,v), and erase(k) functions involve a scan down the list L looking for the entry with key k.

Pseudo-code for implementing these functions is given in Code Fragment 9.4.

[L.begin(), L.end()) denotes all positions of the list L from L.begin() to, but not including, L.end().

Data Structures RoadMap All course Codes version II after Midterm 30

Downloaded by mohmed azam (yousefazam120@gmail.com)

 lOMoARcPSD|39776382

This list-based map implementation is simple, but it is only efficient for very small maps. Every one of the fundamental functions
takes O(n) time on a map with n entries, because each function involves searching through the entire list in the worst case. Thus,
we would like something much faster.

Hash Tables
A map's keys are like "addresses" for its values.

Applications of maps with "addresses" include compilers' symbol tables and registries of environment variables.

The most efficient way to implement a map with "addresses" is to use a hash table.

A hash table consists of two main components: a bucket array and a hash function.

While worst-case running time of map operations in a hash table is O(n), the expected time is O(1).

Data Structures RoadMap All course Codes version II after Midterm 31

Downloaded by mohmed azam (yousefazam120@gmail.com)