Find first `k` maximum occurring words in a given set of strings
Given a huge set of words with duplicates present and a positive integer k, find the first k–maximum occurring words in it.
Category: Heap
Treap Data Structure
A Treap data structure is basically a combination of a binary search tree and a heap.
Find first `k` non-repeating characters in a string in a single traversal
Given a string, find first k non-repeating characters in it by doing only a single traversal of it.
Min Heap and Max Heap Implementation in Java
In previous post, we have introduced the heap data structure and covered heapify-up, push, heapify-down and pop operations. This article covers Java implementation of Priority Queue Data Structure (Max Heap and Min heap).
External Merge Sort Algorithm
The external merge sort algorithm is used to efficiently sort massive amounts of data when the data being sorted cannot be fit into the main memory (usually RAM) and resides in the slower external memory (usually a HDD).
Travelling Salesman Problem using Branch and Bound
Given a set of cities and the distance between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point.
Merge `M` sorted lists each containing `N` elements
Given m sorted lists, each containing n elements, print them efficiently in sorted order.
Find the smallest range with at least one element from each of the given lists
Given M sorted lists of variable length, efficiently compute the smallest range, including at least one element from each list.
Find k’th smallest element in an array
Given an array and a positive integer k, find k’th smallest element in the array… We can easily solve this problem in O(n.log(k)) time by using a max-heap.
Sort a k-sorted array
Given a k–sorted array that is almost sorted such that each of the n elements may be misplaced by no more than k positions from the correct sorted order. Find a space-and-time efficient algorithm to sort the array.
Find k’th largest element in an array
Given an array and positive integer k, find k’th largest element in the array.
Convert max heap to min heap in linear time
Given an array representing a max-heap, in-place convert it into the min-heap in linear time.