Consider the following scenarios:

a. A priority queue is implemented using an array-based heap tree

b. A priority queue is implemented using a linked list.

c. A priority queue is implemented using a linked implementation of heap tree.

Is the priority queue created in the above scenarios dynamic/static and linear/non-linear? Justify your answer in each case.Required to answer. Multi Line Text.

 

Priority queue can be implemented using an array, a linked list, a heap data structure, or a binary search tree. Among these data structures, heap data structure provides an efficient implementation of priority queues.

Hence, we will be using the heap data structure to implement the priority queue in this tutorial. A max-heap is implement is in the following operations. If you want to learn more about it, please visit max-heap and mean-heap.

A comparative analysis of different implementations of priority queue is given below.
------------------------------------------------
Operations	      | peek |	insert	 |  delete  |
------------------|------|-----------|----------|
Linked List	      |  O(1)|	O(n)	 |  O(1)    |
Binary Heap	      | O(1) |	O(log n) |	O(log n)|
Binary Search Tree|	O(1) |	O(log n) |	O(log n)|
-------------------------------------------------

What is a Static Data structure?

In Static data structure the size of the structure is fixed. The content of the data structure can be modified but without changing the memory space allocated to it.

What is Dynamic Data Structure?

In Dynamic data structure the size of the structure in not fixed and can be modified during the operations performed on it. Dynamic data structures are designed to facilitate change of data structures in the run time.

Linear Data Structure:

Data structure where data elements are arranged sequentially or linearly where the elements are attached to its previous and next adjacent in what is called a linear data structure. In linear data structure, single level is involved. Therefore, we can traverse all the elements in single run only. Linear data structures are easy to implement because computer memory is arranged in a linear way. Its examples are array, stack, queue, linked list, etc.

Non-linear Data Structure:

Data structures where data elements are not arranged sequentially or linearly are called non-linear data structures. In a non-linear data structure, single level is not involved. Therefore, we can't traverse all the elements in single run only. Non-linear data structures are not easy to implement in comparison to linear data structure. It utilizes computer memory efficiently in comparison to a linear data structure. Its examples are trees and graphs.

a. A priority queue is implemented using an array-based heap tree

Since array is static and Linear Data structure so we can conclude that array based implementation is static and linear.

b. A priority queue is implemented using a linked list.

Since linked list is dyanamic and Linear Data structure so we can conclude that linked list based implementation is dyanamic and linear.

c. A priority queue is implemented using a linked implementation of heap tree.

We know that tree is non linear and is dyanamic data structure so we can conclude that tree based implementation is dyanamic and non-linear.