Explore

𝟭𝟬 Java Patterns 𝗳𝗼𝗿 𝗦𝗼𝗹𝘃𝗶𝗻𝗴 𝗮 𝗖𝗼𝗱𝗶𝗻𝗴 𝗤𝘂𝗲𝘀𝘁𝗶𝗼𝗻 𝗶𝗻 the 𝐃ata 𝐒tructures and 𝐀lgorithms 𝐈𝐧𝐭𝐞𝐫𝐯𝐢𝐞𝐰

⁠

Learning Outcomes: Training 𝐟𝐨𝐫 𝐏𝐥𝐚𝐜𝐞𝐦𝐞𝐧𝐭𝐬 𝐚𝐧𝐝 𝐃𝐒𝐀 𝐈𝐧𝐭𝐞𝐫𝐯𝐢𝐞𝐰𝐬:

"The Datyssey: A Hero's Journey Through the Labyrinth of Structures and Algorithms"

In the vein of Homer’s Odyssey, we might begin our epic:

"Tell me, O Muse, of that resourceful hero who wandered the vast realms of Data Land, who, after he had plundered the sacred mainframe of Troy, sought to find his way back home. But the children of Silicon, angered by their hubris, unleashed upon themselves a plague of errors and exceptions. None escaped the wrath of the Compiler, the holy keeper of Syntax and Semantics. Now, O Muse, inspire us to tell our hero's tale."

In this sprawling epic, our hero Gwibly, like Odysseus, must navigate a treacherous landscape filled with daunting data structures, cryptic algorithms, and puzzling problems of logic and optimization. Along the way, he meets friends and foes, solves riddles, faces challenges, and grows in wisdom and experience. From humble origins as a single Integer, Gwibly becomes a symbol of persistence, ingenuity, and the indomitable spirit of a true hero of Data Land.

Lecture: Introduction to Data Structures and Algorithms in Java

Introduction

Welcome to this introductory lecture on data structures and algorithms in Java. Data structures and algorithms form the foundation of computer programming and are essential tools in designing robust, efficient software applications. In this lecture, we will discuss some key topics that every developer should be familiar with.

Data Structures

Data structures are fundamental concepts of computer science which helps in organizing and storing data in an efficient manner. They form the building blocks for efficient algorithm design. Here are some of the fundamental data structures:

Arrays: An array stores a fixed-size sequential collection of elements of the same type.

Linked Lists: A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations.

Stacks: A stack is a linear data structure that stores elements in a Last-In/First-Out (LIFO) manner.

Queues: A queue is a linear data structure that stores elements in a First-In/First-Out (FIFO) manner.

Trees: A tree is a nonlinear data structure that simulates a hierarchical tree structure with a set of linked nodes.

Graphs: A graph is a nonlinear data structure consisting of nodes and edges. The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph.

Hashing: Hashing is a technique to convert a range of key values into a range of indexes of an array.

Algorithms

Algorithms are a set of steps to solve a particular problem. They are key to solving complex problems in an efficient and effective way. Some of the key algorithmic techniques are:

Sorting Algorithms: These include popular algorithms like bubble sort, quick sort, merge sort, heap sort, etc.

Searching Algorithms: These include linear search, binary search, etc.

Graph Algorithms: Graph algorithms include depth-first search (DFS), breadth-first search (BFS), Dijkstra's algorithm, etc.

Dynamic Programming: Dynamic Programming is mainly an optimization over plain recursion.

Algorithms and Data Structures in Java

Java offers built-in support for a variety of data structures like Arrays, LinkedList, Stack, Queue, PriorityQueue, HashSet, HashMap, TreeMap etc. And it's quite common to use them to implement algorithms.

For instance, Java's PriorityQueue is typically implemented as a heap, which we discussed in our preceding labs. This allows efficient access to the minimum or maximum element, which can then be used to develop efficient algorithms for problems such as sorting, or finding the kth smallest or largest element.

Conclusion

Understanding and being able to use data structures and algorithms is essential for solving complex computational problems. It allows us to write code that is efficient, maintainable, and easy for others to understand. A strong knowledge of data structures and algorithms is also important for doing well in technical interviews.

In the coming sessions, we will dive deeper into each of these data structures and algorithms, discussing how to implement them in Java, their time and space complexity, and their use cases. We'll also work through examples and problems to apply these concepts. Stay tuned for an exciting journey through data structures and algorithms.

👉🏻 If we are dealing with top/maximum/minimum/closest ‘K' elements among 'N' elements, we will be using a Heap.

Gwibly's Adventure in PriorityQueue

Once upon a time, there was a data object named Gwibly. Gwibly was an instance of an Integer, with a value of 10. He was on his way to meet his girlfriend, Bliss, who was an instance of Integer with a value of 20.

But while hopping from one method to another, he tripped over a misplaced semicolon and fell into a Priority Queue, also known as a heap. He found himself amidst other Integer instances, with values ranging from 1 to 100.

Panic swept over Gwibly as he realized that escaping wouldn't be as simple as he thought. Priority Queues have a strict rule: The data object with the highest priority (in this case, the lowest value, as it's a Min Heap), gets to leave the queue first.

Gwibly, with his value of 10, saw data objects with values less than his: 3, 5, 1, 8... He quickly realized that he needed to somehow increase his priority. But how could an Integer change its value? Gwibly knew it was immutable!

Suddenly, an idea came to Gwibly: He couldn't change his value, but he could still try to convince other data objects to let him out. Gwibly, who was quite charming, started a conversation with the current head of the queue, a shy integer of value 1.

"Hey there, friend!" he started, "I'm in a bit of a bind. I've fallen into this queue by accident and I desperately need to get out to meet my girlfriend. Would you let me take your place?"

The integer with value 1, was quite sympathetic and decided to help Gwibly. He whispered back, "I'm sorry, Gwibly, but I can't let you take my place. The Heap Property rules are strict. But I can tell you a secret."

Gwibly listened eagerly.

"Whenever a poll() operation is called on the queue, the object with the highest priority gets removed. And currently, that's me. But you see, once I'm gone, the queue will reorder itself to maintain the heap property. It will percolate up the next highest priority element. It will continue to do this, each time poll() is called, until it's your turn."

Gwibly was overjoyed! All he had to do was wait for his turn. He thanked the integer of value 1, and braced himself.

One by one, each time poll() was called, the Integer with the highest priority - the smallest value - was removed from the queue. Gwibly saw them all leave: 1, 2, 3... and so on. Finally, after what seemed like an eternity, it was his turn. Gwibly, with his value of 10, was now the highest priority!

With a whoosh, Gwibly was removed from the Priority Queue, having survived his unexpected detour. Reoriented, he promptly continued his journey, more determined than ever to reach Bliss.

And the moral of the story? Even in a Priority Queue, every element has its moment of glory - it just needs a bit of patience. And remember, in a Min Heap based Priority Queue, the smallest element always takes precedence.

Heap and Priority Queue Lab

Objective:

This lab aims to teach you how to implement a Heap in Java. You will also learn about the concept of Priority Queue and how to use it to find the top/maximum/minimum/closest 'K' elements among 'N' elements.

Lab Task 1: Implementing a Heap

Java Heap and Its Applications

Introduction

A heap is a specialized tree-based data structure that satisfies the heap property. There are two types of heaps: max-heap and min-heap. In a max heap, for any given node I, the value of I is greater than or equal to the values of its children. In a min heap, the value of I is less than or equal to the values of its children.

Heap is an important data structure in Java, not just in the form of the binary heap but also the memory heap, which is where Java objects live. Today, we'll focus on the binary heap data structure, which is commonly used in the implementation of priority queues and the heapsort algorithm.

Java's PriorityQueue

Java's built-in PriorityQueue class is a great example of a heap implementation. It uses a variant of a binary heap and allows us to add elements into the queue with an offer() or add() method and retrieve and remove the highest priority element with poll(). The priority of the elements is determined either by their natural order (if they implement Comparable) or by a custom Comparator provided at queue construction time.

Applications of Heap

Let's talk about some interesting applications of a heap.

Priority Queues: Priority queues are a type of data structure in which each element is associated with a priority and is served according to its priority. If elements with the same priority occur, they are served according to their ordering in the queue. Java's PriorityQueue class is a classic application of a heap.

HeapSort: HeapSort is an efficient sorting algorithm implemented using a Binary Heap. The idea is to build a max heap of elements present in the array. The largest element, which is the root of the max heap, is then replaced with the last element of the heap followed by reducing the size of heap by 1. This process is repeated until all the items are sorted.

Kth Largest or Kth Smallest Element: A heap can be used to efficiently find the Kth largest (or smallest) element in an array. This can be done by creating a min (or max) heap of size k and iterating through the rest of the elements to find the Kth largest or smallest element.

Median of a Stream: Heaps can be used to efficiently compute the median of a stream of numbers. This can be achieved by dividing the numbers into two halves - one half is a max heap (representing the smaller half of the numbers) and the other is a min heap (representing the larger half of the numbers). The median is then computed based on the roots of the two heaps.

Dijkstra's Algorithm: The heaps are used in the implementation of Dijkstra's algorithm which is used to find the shortest path from one node to all other nodes in a weighted graph.

In conclusion, heaps are extremely versatile and useful data structures. Their ability to maintain the highest or lowest element at the root, depending on whether it's a max-heap or min-heap, and to add, delete and sort elements efficiently, makes them useful in a wide variety of applications, from sorting algorithms and priority queues to graph algorithms.

class MaxHeap {

private int[] heap;

private int size;

public MaxHeap(int capacity) {

heap = new int[capacity];

}

public void insert(int value) {

if(size == heap.length) {

throw new IndexOutOfBoundsException("Heap is full");

}

heap[size] = value;

fixHeapAbove(size);

size++;

}

private void fixHeapAbove(int index) {

int newValue = heap[index];

while(index > 0 && newValue > heap[getParent(index)]) {

heap[index] = heap[getParent(index)];

index = getParent(index);

}

heap[index] = newValue;

}

private int getParent(int index) {

return (index - 1) / 2;

}

Let's create a main class to run the MaxHeap implementation. We'll add several items to the heap, and display the structure of the heap after each insertion.

Here's a Main class that showcases usage of MaxHeap:

public class Main {

public static void main(String[] args) {

MaxHeap heap = new MaxHeap(10);

heap.insert(80);

heap.insert(75);

heap.insert(60);

heap.insert(68);

heap.insert(55);

heap.insert(40);

heap.insert(52);

heap.insert(67);

heap.printHeap();

}

And here's an extended version of the MaxHeap class with an additional printHeap method for visualization purposes:

class MaxHeap {

private int[] heap;

private int size;

public MaxHeap(int capacity) {

heap = new int[capacity];

}

public void insert(int value) {

if(size == heap.length) {

throw new IndexOutOfBoundsException("Heap is full");

}

heap[size] = value;

fixHeapAbove(size);

size++;

}

private void fixHeapAbove(int index) {

int newValue = heap[index];

while(index > 0 && newValue > heap[getParent(index)]) {

heap[index] = heap[getParent(index)];

index = getParent(index);

}

heap[index] = newValue;

}

private int getParent(int index) {

return (index - 1) / 2;

}

public void printHeap() {

for(int i=0; i<size; i++) {

System.out.println(heap[i]);

}

After running the Main class, the console output should be the elements of the heap in the order they exist in the underlying array. The heap property is maintained, i.e., each parent is greater than or equal to its children. Please note that the elements might not be sorted because the heap property only guarantees partial order.

Lab Task 2: Using Java's PriorityQueue

Java provides a built-in PriorityQueue class that implements a priority heap.

We'll use this to find the top 'K' numbers in an array.

import java.util.PriorityQueue;

public class Main {

public static void main(String[] args) {

int[] nums = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 9};

int k = 3;

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

for(int num: nums) {

pq.add(num);

if(pq.size()>k) {

pq.poll();

}

while(!pq.isEmpty()) {

System.out.println(pq.poll());

}

What does the poll method do in priorityqueue

The poll() method is a part of the PriorityQueue class in Java. The PriorityQueue class is a queue data structure implementation where the objects are processed based on their priority. It is different from the standard queue as it implements a priority heap where elements are ordered as per their natural ordering or a custom comparator provided at queue construction time.

The poll() method in PriorityQueue is used to retrieve and remove the head of this queue, or return null if this queue is empty. The head of this PriorityQueue instance is the least element with respect to the specified ordering. If multiple elements are tied for the least value, the head is one of those elements.

Let's understand it with an example:

import java.util.PriorityQueue;

public class Main {

public static void main(String[] args) {

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

numbers.add(4);

numbers.add(2);

numbers.add(1);

System.out.println("PriorityQueue: " + numbers);

int number = numbers.poll();

System.out.println("Removed Number: " + number);

System.out.println("Updated PriorityQueue: " + numbers);

}

How is the priority in a priority queue established

Priority in a PriorityQueue is determined based on the elements' natural ordering or by a Comparator that is provided at PriorityQueue creation time. Let's dive into these two scenarios a bit more:

Natural Ordering: If the elements in the PriorityQueue are of a class that implements the Comparable interface, the natural ordering of those elements is used. For example, when you insert Integer objects into a PriorityQueue, they are ordered by their natural ordering - numerically.

Custom Comparator: You can also provide a Comparator while creating the PriorityQueue which allows you to control how the elements will be prioritized and ordered. For example, you could have a Person class where each person has a name and age, and you could have a PriorityQueue of persons prioritized by age.

Here's a quick example for each scenario:

Natural Ordering Example:

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

pq.add(5);

pq.add(1);

pq.add(3);

System.out.println(pq.poll()); // Outputs "1"

System.out.println(pq.poll()); // Outputs "3"

System.out.println(pq.poll()); // Outputs "5"

Custom Comparator Example:

Comparator<Person> ageComparator = new Comparator<Person>() {

@Override

public int compare(Person p1, Person p2) {

return Integer.compare(p1.getAge(), p2.getAge());

}

};

PriorityQueue<Person> pq = new PriorityQueue<>(ageComparator);

pq.add(new Person("Alice", 30));

pq.add(new Person("Bob", 20));

pq.add(new Person("Charlie", 25));

System.out.println(pq.poll().getName()); // Outputs "Bob"

System.out.println(pq.poll().getName()); // Outputs "Charlie"

System.out.println(pq.poll().getName()); // Outputs "Alice"

In the above example, the Person with the smallest age is considered of higher priority, thus it would be the first to be retrieved by poll() method.

In both cases, when you call poll(), it will remove and return the highest-priority element according to the natural ordering or the Comparator provided.

Remember, PriorityQueue does not actually sort the elements. It just orders the elements internally according to the priority such that poll() always returns the highest-priority element.

Output:

PriorityQueue: [1, 4, 2]

Removed Number: 1

Updated PriorityQueue: [2, 4]

As seen in the example above, the poll() method removed the element with the least value, which was 1 in this case.

It's important to note that poll() method runs in O(log n) time for a PriorityQueue which means it's quite efficient for a large number of elements.

That's a brief explanation of the poll() method in PriorityQueue in Java. It's a very useful method when you want to retrieve and remove the least element from a PriorityQueue, which can be very helpful in a variety of scenarios in programming.what does the fixHeapAbove(size) method do?

The fixHeapAbove(size) method is typically used in heap data structures to maintain the heap property after a new element is inserted at the end (bottom) of the heap. It is applicable in the context of both min-heaps and max-heaps.

Assuming 'size' is the index of the newly inserted element, this method will compare the inserted element with its parent (which is at index (size - 1) / 2 in a zero-based array representation of the heap). If the newly inserted element violates the heap property with respect to its parent, it swaps the two.

In a max heap, if the new element is greater than its parent, it will continue to swap the new element with its parent until it is no longer greater than its parent or it becomes the root (i.e., reaches the top of the heap).

In a min heap, if the new element is less than its parent, it will continue to swap the new element with its parent until it is no longer less than its parent or it becomes the root.

This process is also known as "percolate up" or "bubble up" in heap terminology. It ensures that the heap property is restored after the insertion of a new element. Note that the exact implementation and method name might vary based on the context or programming language.

Define what the heap property is {Hierarchical Ordinality}

The heap property is a specific characteristic of a binary heap data structure, which is a complete binary tree. There are two kinds of binary heaps: min-heaps and max-heaps, each having its own specific heap property:

Min-Heap Property: In a min-heap, for any given node I, the value of I is greater than or equal to the values of its children. In other words, the smallest element is the root of the tree.

Max-Heap Property: In a max-heap, for any given node I, the value of I is less than or equal to the values of its children. In other words, the largest element is the root of the tree.

It's important to note that while a heap must follow the min-heap or max-heap property, it doesn't need to be a sorted structure. The property only applies vertically (parent-child), not horizontally (between siblings or across different levels).

Maintaining the heap property is fundamental to the operations of a binary heap, such as insertion, deletion, and heapify. When these operations are performed, if the heap property is violated, the heap must be "re-heapified" to restore the property. This is typically done through "percolate up" or "percolate down" (also known as "bubble up" or "bubble down") operations.

This will give the top 3 numbers from the array.

Questions:

What does the insert method in the MaxHeap class do?

What does the fixHeapAbove method in the MaxHeap class do?

How does the PriorityQueue determine the order of its elements?

Why do we check if(pq.size()>k) in the above code?

What does pq.poll() do?

Challenge:

Modify the code above to find the minimum 'K' elements from the array.

Homework:

Implement a min-heap in Java.

Use the min-heap to find the 'K' closest numbers to a given number 'X' in an array.

Use Java's PriorityQueue to find the 'K' closest numbers to a given number 'X' in an array.

Submission:

Submit your answers to the questions and your code for the challenge and homework in a document. Ensure your code is well-commented to explain what each part does.

👉🏻 If the given input is a sorted array or a list, we will either be using Binary Search or the Two Pointers. 👉🏻 If we need to try all combinations (or permutations) of the input, we can either use Backtracking or Breadth First Search. 👉🏻 Most of the questions related to Trees or Graphs can be solved either through Breadth First Search or Depth First Search. 👉🏻 Every recursive solution can be converted to an iterative solution using a Stack. 👉🏻 For a problem involving arrays, if there exists a solution in O(n^2)time and O(1) space, there must exist two other solutions: 1) Using a HashMap or a Set for O(n) time and O(n) space, 2) Using sorting for O(n log n) time and O(1) space. 👉🏻 If a problem is asking for optimization (e.g., maximization or minimization), we will be using Dynamic Programming. 👉🏻 If we need to find some common substring among a set of strings, we will be using a HashMap or a Trie. 👉🏻 If we need to search/manipulate a bunch of strings, Trie will be the best data structure. 👉🏻 If the problem is related to a LinkedList and we can't use extra space, then use the Fast & Slow Pointer approach.

Want to print your doc?
This is not the way.

Try clicking the ⋯ next to your doc name or using a keyboard shortcut (

CtrlP

) instead.