Priority,Heap,time & space complexity

Q#1: What is priority Queue. How many types exist. Explain each of them in detail.

Priority Queue:

A priority queue is a queue in which insertion and deletion of items from any position in the queue are done based on some property (such as priority of task).

Priority queue contains data items which have some preset priority. While removing an element from a priority queue, the data item with the highest priority is removed first.

In a priority queue, insertion is performed in the order of arrival and deletion is performed based on the priority

Types of Priority

 

1.Ascending Priority: An ascending order priority queue gives the highest priority to the lower number in that queue.

Example:   you have six numbers in the priority queue that are 4, 8, 12, 45, 35, 20. Firstly, you will arrange these numbers in ascending order. The new list is as follows: 4, 8, 12, 20. 35, 45. In this list, 4 is the smallest number. Hence, the ascending order priority queue treats number 4 as the highest priority.

2.Descending Priority: A descending order priority queue gives the highest priority to the highest number in that queue. 

Example:  You have six numbers in the priority queue that are, 8, 4, 12, 45, 35, 20. Firstly, you will arrange these numbers in ascending order. The new list is as follows: 45, 35, 20, 12, 8, 4. In this list, 45 is the highest number. Hence, the descending order priority queue treats number 45 as the highest priority

Q#2: Differentiate between recursion and iteration with the help of examples .

Criteria	Recursion	Iteration
Definition	When a function calls itself	When some set of instructions  are executed repeatedly
Implementation	Implementation using calls	Implementation using loops
Speed	Slower in execution	Faster in execution
Code size	Code size is generally smaller and simpler	Code size is generally bigger
Memory usage	Uses stack memory to store local variables and parameters	Do not use memory except initializing control variables
Examples	#include<iostream>. Using namespace std;  int sum(int num) { if (num != 0) { return num + sum(num-1) } return 0; } int main() { int num; cout << "Enter the number : "; cin >> num; cout << "Sum is" <<sum(num)<<endl; }	#include<iostream> using namespace std; int main() {   int n;   for(n=l; n<=10; n++)     cout<<n<<" "; // body of the loop     cout<<"\n This is an example of for loop!! !";     //next statement in sequence return 0; }

 

Q#3: what is heap? Explain Min Heap and Max Heap with help of example?

A Heap is a special Tree-based data structure in which the tree is a complete binary tree. Since a heap is a complete binary tree, a heap with N nodes has log N height. It is useful to remove the highest or lowest priority element. It is typically represented as an array. There are two types of Heaps in the data structure.

	Min Heap	Max Heap
1.	In a Min-Heap the key present at the root node must be less than or equal to among the keys present at all of its children.	In a Max-Heap the key present at the root node must be greater than or equal to among the keys present at all of its children.
2.	In a Min-Heap the minimum key element present at the root.	In a Max-Heap the maximum key element present at the root.
3.	A Min-Heap uses the ascending priority.	A Max-Heap uses the descending priority.
4.	In the construction of a Min-Heap, the smallest element has priority.	In the construction of a Max-Heap, the largest element has priority.
5.	In a Min-Heap, the smallest element is the first to be popped from the heap.	In a Max-Heap, the largest element is the first to be popped from the heap
	Example         1        / \       2   3      / \ / \     4   5 6  7	Example         10        /  \       9    8      / \  / \     7   6 5  4

 

Q#4:What is Time Complexity and Space Complexity? How can we calculate both the Complexities. Make the comparison between them in detail.

 Time Complexity:

Time complexity is defined in terms of how many times it takes to run a given algorithm, based on the length of the input. Time complexity is a type of computational complexity that describes the time required to execute an algorithm.

Space Complexity

When an algorithm is run on a computer, it necessitates a certain amount of memory space. The amount of memory used by a program to execute it is represented by its space complexity. Because a program requires memory to store input data and temporal values while running, the space complexity is auxiliary and input space.

Importance of Space and Time Complexity:

Calculation of Time Complexity:

Assume you have a set of numbers S= (10, 50, 20, 15, 30)

There are numerous algorithms for sorting the given numbers. However, not all of them are effective. To determine which is the most effective, you must perform computational analysis on each algorithm.

 Asymptotic Notations:

Asymptotic Notations are programming languages that allow you to analyze an algorithm's running time by identifying its behavior as its input size grows. This is also referred to as an algorithm's growth rate.

Time Complexity  VS  Space Complexity

Time Complexity:

• Measures the amount of time an algorithm takes to run.
• It focuses on analyzing the growth rate of the running time as the input size increases.
• Time complexity is denoted using Big O notation.
• The time complexity is determined by analyzing the number of operations performed by the algorithm.
• It considers the worst-case scenario, indicating the maximum time required for any input size.
• Optimizing time complexity aims to reduce the overall running time of the algorithm.
• Time complexity is crucial for optimizing algorithm efficiency, especially for large input sizes.

Space Complexity:

• Estimates the amount of memory space an algorithm requires.
• It focuses on analyzing the growth rate of the memory usage as the input size increases.
• Space complexity is also denoted using Big O notation.
• The space complexity considers the memory used by variables, inputs, outputs, and any auxiliary data structures.
• It provides an understanding of how the algorithm's memory requirements scale with increasing input size.
• Optimizing space complexity aims to minimize the memory usage of the algorithm.
• Space complexity is important for optimizing memory efficiency, especially in resource-constrained environments.

 

Major Differences

1. Measure:

Time complexity measures the running time of an algorithm, while space complexity estimates the memory space required.

2. Growth Rate:

Time complexity analyzes the growth rate of running time, while space complexity analyzes the growth rate of memory usage.

3. Notation:

 Both complexities are expressed using Big O notation.

4. Analysis:

Time complexity considers the number of operations performed, while space complexity considers the memory used by variables and data structures.

5. Worst-case Scenario:

Time complexity analyzes the worst-case scenario, while space complexity provides an estimation for all input sizes.

6. Optimization Focus:

 Time complexity optimization aims to reduce running time, while space complexity optimization aims to minimize memory usage.

Q#5:Difference between stack and heap?

Stack Ø  The stack is a place in the computer memory where all the variables that are declared and initialized before runtime are stored. Ø  It is a temporary storage memory, if       you come out of the program the memory of the variable will not be there. Ø  Any data on the stack for a function will automatically be deleted. Ø  In stack data data is added or removed in last-in-first-out-manner (LIFO)  Ø  The stack has a fixed size Ø  Both stack and heap are stored on the RAM Ø  If there is not enough space on the stack to handle the memory being assigned to it, a stack overflow occurs. Ø  Example: For Stack overflow #include <iostream> Using namespace std: int main() { int nStack[100000000]; return 0; } Causes stack overflow Program will crash

Ø  Heap: Ø  Heap is an area of memory used for dynamic memory allocation. Ø  The heap is the memory used by program to store global variables. Ø  Variables on the heap must be destroyed manually. Ø  Any data on the heap will remain there until it's manually deleted by the programmer. Ø  If the current size of the heap is too small to accommodate new memory, then more memory can be added to the heap by the operating system. Ø  Does not have size restrictions on variable size Ø  Heap memory is slower than stack

Q#6:Implement priority queue and all its type?

#include <iostream>

#include <queue>

using namespace std;

int main() {

 

    priority_queue<int, vector<int>, greater<int> >ascendingPriorityQueue;

    priority_queue<int> descendingPriorityQueue;

 

    // Insert elements into the ascending priority queue

    ascendingPriorityQueue.push(5);

    ascendingPriorityQueue.push(2);

    ascendingPriorityQueue.push(8);

    ascendingPriorityQueue.push(1);

    ascendingPriorityQueue.push(7);

 

    // Insert elements into the descending priority queue

    descendingPriorityQueue.push(5);

    descendingPriorityQueue.push(2);

    descendingPriorityQueue.push(8);

    descendingPriorityQueue.push(1);

    descendingPriorityQueue.push(7);

    cout << "Ascending Priority Queue (Min-Heap):" << endl;

    while (!ascendingPriorityQueue.empty()) {

        cout << ascendingPriorityQueue.top() << " ";

        ascendingPriorityQueue.pop();

    }

    cout << endl;

    cout << "Descending Priority Queue (Max-Heap):" << endl;

    while (!descendingPriorityQueue.empty()) {

        cout << descendingPriorityQueue.top() << " ";

        descendingPriorityQueue.pop();

    }

    cout << endl;

 

    return 0;

}

Output: