Last Updated on December 14, 2022 by Prepbytes
Data structure refers to a collection of data with well-defined operationsIn this article, we’ll be discussing Data structures in Java, The term data, behaviour, or properties. A data structure is a special manner of storing or organising data in computer memory so that we can use it effectively.
So, in this article, we are going to discuss 2 very important data structures viz, Queue and Heap (Priority Queue).
Data Structures in Java are an important part of Programming. Get a better understanding of problems by watching these video tutorials created by expert mentors at Prepbytes.
Queue in Java
Let us first talk about the queue data structure in Java.
As shown in the image above, a queue is a linear data structure that can be imagined as if it is open from both ends. The ends of a queue are called front and rear. A Queue is a FIFO data structure.
This means that it follows the FIFO principle for the insertion and removal of elements. FIFO stands for First in First out. So, the element that is entered first into the queue will be the first element to be removed from the queue as well.
Creating a Queue:
A queue is an Interface in Java. This means that it can be implemented via multiple classes. So, if we create a reference to Queue, we can create the object of a Linked List, ArrayDeque, PriorityQueue, etc.
However, the functionality of queue data structure is best provided by ArrayDeque. So, we mostly use ArrayDeque Class to create a Queue object if we require the functionalities of a queue only.
A program to create a queue is shown below.
import java.util.*;
public class Main {
public static void main(String[] args) {
//Queue is an Interface
//ArrayDeque is a Class
//The reference q is of interface Queue
//Object is of type ArrayDeque
Queue<Integer> q = new ArrayDeque<>();
}
}
To maintain the FIFO order, a queue allows insertion only from the rear end and allows deletion only from the front of the queue. Let’s understand these operations of a queue in more detail.
Enqueue:
Pushing a value inside a queue is called enqueue operation. As already discussed, enqueue operation will happen only from the rear end of the queue.
Let us see some enqueue operations.
In the above image, element 10 was inserted into the queue. As shown in the image, the element is inserted from the rear end of the queue.
Let us enqueue another value into the queue.
Again, we can see that 20 was inserted from the rear end of the queue.
So, let us insert some more values into the queue.
Time Complexity of Enqueue:
The time complexity for the enqueue operation in a queue is O(1). This is because we don’t have to shift any elements as every time, we are inserting from the rear end of the queue only.
In Java, add() method is used to perform the enqueue operation in the queue. The method add(), by default, inserts the element to the rear end of the queue. The Java program to perform the enqueue operation is shown below.
import java.util.*;
public class Main {
public static void main(String[] args) {
Queue<Integer> q = new ArrayDeque<>();
q.add(10);
q.add(20);
q.add(30);
q.add(40);
q.add(50);
System.out.println(q);
}
}
Dequeue:
Removing an element from the queue is called a dequeue operation. As already discussed, the dequeue operation in the queue will always happen from the front end of the queue.
Consider the queue shown below.
Here, when we perform the dequeue operation, 10 will be removed from the queue as shown below.
Now, when we perform the dequeue operation again, 20 will be removed from the queue.
So, this is how the dequeue operation is performed.
Time Complexity of Dequeue:
The time complexity of the dequeue operation is also O(1). This is because we just have to remove the very first element of the queue and we do not have to shift any element.
In Java, the remove() method is used to perform the dequeue operation from the queue. This method by default removes an element from the front of the queue.
So, let us see a program to use the remove() method.
import java.util.*;
public class Main {
public static void main(String[] args) {
Queue<Integer> q = new ArrayDeque<>();
q.add(10);
q.add(20);
q.add(30);
q.add(40);
q.add(50);
System.out.println(q);
q.remove();
System.out.println(q);
q.remove();
System.out.println(q);
}
}
Size:
We can get the size of the queue using the size() method in Java. The time complexity of this method is also O(1).
import java.util.*;
public class Main {
public static void main(String[] args) {
Queue<Integer> q = new ArrayDeque<>();
q.add(10);
q.add(20);
q.add(30);
q.add(40);
q.add(50);
System.out.println(q);
System.out.println(q.size());
q.remove();
System.out.println(q);
System.out.println(q.size());
q.remove();
System.out.println(q);
System.out.println(q.size());
}
}
So, these are some of the basic functions of a queue data structure. In Java, there are a lot more functions available to us. However, the basic understanding and implementation of this data structure revolve around the above-discussed functions.
Test your data structure skills by taking this Data Structures in Java Mock Test designed by experienced mentors at PrepBytes.
Let us now discuss the Heap data structure.
Heaps in Java
A heap is a tree-based data structure. In Java, a Heap is available as PriorityQueue. Basically, it is implemented as a heap in the back-end of Java and it is available to us as a PriorityQueue for usage.
A heap is such a tree-based data structure that every parent node will have a higher priority than its children. If this is the case, the highest priority element will be at the root of the tree and we will be able to fetch it in O(1) time.
Please note that this property of a parent having higher priority than children is called Heap-Order Property. In a heap, every node has to follow this property.
Also, a heap is always a complete binary tree. This means that if there are L numbers of levels, then the L-1 levels are complete and the last level has nodes starting from the left-most node.
Heap can be of 2 types, min heap and max heap. Let us understand them with examples.
Max Heap
In a max heap, the higher element has a higher priority. A max heap is a heap where every parent node is greater than its children. Now, there is no limit on the children’s relative priority to each other. This means that the left child can be greater than the right or the right can be greater than the left. However, since it is a max heap, the parent has to be greater than both of them.
As we can see, every parent node has a value greater than its children. However, there is no specific order of whether the left child will be greater or the right.
Min Heap
In a min heap, the lower element has a higher priority. A min-heap is a heap where every parent node is smaller than its children. Now, there is no limit on the children’s relative priority to each other. This means that the left child can be smaller than the right or the right can be smaller than the left. However, since it is a min heap, the parent has to be smaller than both of them.
As we can see, every parent node has a value less than its children. However, there is no specific order of whether the left child will be smaller or the right.
Creating a Heap (Priority Queue) in Java
PriorityQueue is a Class in Java. So, we can create both the reference and object of PriorityQueue. However, we have discussed in the Queue Data structure above that Queue is an interface. So, we can also have a reference of Queue and an object of PriorityQueue in Java.
In Java, the PriorityQueue created by default is a Min-Heap.
Let us write some code to create PriorityQueue in Java.
import java.util.*;
public class Main {
public static void main(String[] args) {
//reference and object both of PriorityQueue
PriorityQueue<Integer> pq= new PriorityQueue<>();
//reference of Queue and object of PriorityQueue
Queue<Integer> q = new PriorityQueue<>();
}
}
Add:
The add() method in the priority queue helps us to add an element in the priority queue. Since PriorityQueue is an abstract data structure in Java i.e. we have implemented it using heap but we use it as a priority queue, we can’t really say anything about the exact position of an element in the priority queue.
However, the addition takes place keeping in mind that we have to maintain a min-heap (by default) and lower elements have higher priority.
The time complexity of insertion in a priority queue is O(log2N). Let us see some code to insert some elements in the priority queue.
import java.util.*;
public class Main {
public static void main(String[] args) {
PriorityQueue<Integer> pq= new PriorityQueue<>();
pq.add(10);
pq.add(5);
pq.add(50);
pq.add(20);
pq.add(30);
System.out.println(pq);
}
}
Peek:
The peek() method returns the topmost element in the priority queue. It is the element with the highest priority. Since by default, min-heap is implemented, we will get the lowest element in the priority queue using the peek() method.
For instance, if a priority queue contains {10,40,50,20,5,17,19}, we can’t say anything about the order of these elements (i.e. index based order) ; however, on applying the peek() method, we will get 5.
The time complexity of the peek() method is O(1).
Now, let us write a program to test the peek() method.
import java.util.*;
public class Main {
public static void main(String[] args) {
PriorityQueue<Integer> pq= new PriorityQueue<>();
pq.add(10);
pq.add(5);
pq.add(50);
pq.add(20);
pq.add(30);
System.out.println(pq);
System.out.println(pq.peek());
}
}
Remove:
This method removes the highest priority element from the priority queue. Since by default, min-heap is implemented, the smallest element from the queue is removed.
The time complexity of remove() operation is O(log2n). Let us now write the code for the same.
import java.util.*;
public class Main {
public static void main(String[] args) {
PriorityQueue<Integer> pq= new PriorityQueue<>();
pq.add(10);
pq.add(5);
pq.add(50);
pq.add(20);
pq.add(30);
System.out.println(pq);
System.out.println(pq.peek());
pq.remove();
System.out.println(pq);
System.out.println(pq.peek());
}
}
Max-Heap Creation:
We have talked about the basic methods of a PriorityQueue in Java. Although there are a lot more methods, these methods are sufficient to understand and work with the basics of Heap data structure. However, we know that Java creates a min-heap by default.
So, if we want to create a max-heap, we have to use the method Collections.reverseOrder(). This method is actually a comparator that has to be passed as a parameter during the constructor calling while creating a PriorityQueue.
This changes the behaviour of PriorityQueue from min-heap to max-heap.
Let us implement this in a program.
import java.util.*;
public class Main {
public static void main(String[] args) {
PriorityQueue<Integer> pq= new PriorityQueue<>(Collections.reverseOrder());
pq.add(10);
pq.add(5);
pq.add(50);
pq.add(20);
pq.add(30);
System.out.println(pq);
System.out.println(pq.peek());
pq.remove();
System.out.println(pq);
System.out.println(pq.peek());
}
}
Also, you can test your data structure skills by taking this Data Structures in Java Mock Test designed by experienced mentors at PrepBytes.
We tried to discuss Data Structures in Java in this article. We hope this article gives you a better understanding of the basics of Data Structures in Java. Add New