Category: Heap

Implementation of Treap Data Structure (Insert, Search and Delete)

In this post, we will implement Treap Data Structure and perform basic operations like insert, search and delete on it.

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.

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.

Treap Data Structure

A Treap Data Structure is basically a combination of a binary search tree and a heap.   Binary Search Trees – Deletions and additions of nodes can make the tree unbalanced (heavier on sides, therefore, the property we value about BSTs, the ability to distribute data by equal divisions, goes out of whack). Therefore we …

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.

Min Heap and Max Heap Implementation in Java

Implement Heap data structure in Java.

External Merge Sort Algorithm

We can efficiently sort massive amounts of data using External Merge Sort Algorithm, when the data being sorted don’t fit into the main memory (which is usually RAM) and resides in the slower external memory (which is usually a hard disk).

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.