Heap Sort – Java Implementation

What is Heap Sort?? Heap sort is comparison based sorting algorithm. Heap sort is considered as improved selection sort, it divides the input into sorted and unsorted region. The improvement from selection sort is to use Heap Data Structure instead of using linear search algorithm to reduce of the time complexity. Pre-requisite: Binary Heap (min … Read more

Dijkstra’s – Shortest Path Algorithm (SPT) – Adjacency List and Priority Queue – Java Implementation

Earlier we have seen what Dijkstra’s algorithm is and how it works. In this article, we will see its implementation using the adjacency list and Priority Queue. brief: What is Dijkstra’s algorithm? Dijkstra algorithm is a greedy algorithm. It finds a shortest-path tree for a weighted undirected graph. This means it finds the shortest paths between nodes … Read more

Prim’s – Minimum Spanning Tree (MST) |using Adjacency List and Priority Queue with decrease key

Earlier we have seen what is Prim’s algorithm is and how it works. In this article we will see its implementation using adjacency list and Priority Queue. We strongly recommend to read – prim’s algorithm and implementation of priority queue. Example: Implementation – Adjacency List and Priority Queue with decrease key In last article we … Read more

Shortest Range in K-sorted Lists

Objective: You have k lists of sorted integers. Find the smallest range that includes at least one number from each of the k lists. This is very nice and tricky solution, This problem was asked in the Google interview for software engineer position. Example: Smallest range will be 2, [1,3], it will contain 3 from list … Read more

Generate Maximum revenue by selling K tickets from N windows

Objective: Given ‘N’ windows where each window contains certain number of tickets at each window. Price of a ticket is equal to number of tickets remaining at that window. Write an algorithm to sell ‘k’ tickets from these windows in such a manner so that it generates the maximum revenue. This problem was asked in … Read more

Find the Kth Smallest/Largest Element in an Array

Objective: Given an array of integers. find the Kth Smallest/largest element in the array. Example: int[] A = { 1, 2, 10, 20, 40, 32, 44, 51, 6 }; K=4. 4th smallest element in given array: 10 Approach: (Kth Smallest Element) Use min-Heap. (Click here to read about Priority Queue). Insert all the elements in … Read more

Priority Queue in Data Structure

Earlier in we have seen Min-Heap and Max-Heap Implementation. Priority Queue is its built-in implementation in Java. In this article we will see how to perform Min-Heap and Max-Heap using Priority Queue. Brief: A priority queue is an abstract data type where each element has a “priority” assigned to it. So the element with the … Read more

Merge K Sorted Arrays

Objective: Given k sorted array, write an algorithm to merge Them into One sorted array.

Example :

int[][] A = new int[5][];

A[0] = new int[] { 1, 5, 8, 9 };
A[1] = new int[] { 2, 3, 7, 10 };
A[2] = new int[] { 4, 6, 11, 15 };
A[3] = new int[] { 9, 14, 16, 19 };
A[4] = new int[] { 2, 4, 6, 9 };

[1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 9, 9, 9, 10, 11, 14, 15, 16, 19]

Read more

Binary Min-Max Heap Implementation

A binary heap is a heap data structure created using a binary tree. binary tree has two rules – Binary Heap has to be a complete binary tree at all levels except the last level. This is called a shape property. All nodes are either greater than equal to (Max-Heap) or less than equal to … Read more