Convert Min Heap to Max Heap in O(n) time
Given an array representing a Min Heap, convert Min Heap into a Max Heap. The conversion should be done inplace and in linear time.
Category: Heap
Merge M sorted lists of variable length
Given M sorted lists of variable length, print them in sorted order efficiently.
Huffman Coding Compression Algorithm
Huffman Coding (also known as Huffman Encoding) is a algorithm for doing data compression and it forms the basic idea behind file compression. This post talks about fixed length and variable length encoding, uniquely decodable codes, prefix rules and construction of Huffman Tree.
Find first k non-repeating characters in a string in single traversal
Given a string, find first K non-repeating characters in it by doing only single traversal of it. For example, if the string is ABCDBAGHCHFAC and K = 3, output would be D G F
Min Heap and Max Heap Implementation in Java
Implement Heap data structure in Java. Email Address We have already introduced heap data structure in previous post and covered heapify-up, push, heapify-down and pop operations. In this post, java implementation of Max Heap and Min heap is discussed.
External Sorting (External merge sort)
External sorting is a term for a class of sorting algorithms that can handle massive amounts of data. External sorting is required when the data being sorted do not fit into the main memory of a computing device (usually RAM) and instead they must reside in the slower external memory (usually a hard drive).
Travelling Salesman Problem using Branch and Bound
Given a set of cities and 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 in sorted order efficiently.
Find 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 that includes at-least one element from each list.
Find K’th smallest element in an array
Given an array and positive integer k, find k’th smallest element in the array.
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.