Return k’th largest element in a stream
Given an infinite stream of integers, return the element representing the k’th largest element in the stream.
Category: Heap
Connect `n` ropes with minimal cost
Given n ropes of different lengths, connect them into a single rope with minimum cost. Assume that the cost to connect two ropes is the same as the sum of their lengths.
Convert a Binary Search Tree into a Min Heap
Given a binary search tree (BST), efficiently convert it into a min-heap. In order words, convert a binary search tree into a complete binary tree where each node has a higher value than its parent’s value.
Check if a binary tree is a min-heap or not
Given a binary tree, check if it is a min-heap or not. In order words, the binary tree must be a complete binary tree where each node has a higher value than its parent’s value.
Construct a Cartesian tree from an inorder traversal
Write an efficient algorithm to construct a Cartesian tree from inorder traversal. A Cartesian tree is a binary tree with the heap property: the parent of any node has a smaller value than the node itself.
Implementation of Treap Data Structure (Insert, Search, and Delete)
This post will implement a treap data structure, a combination of a binary search tree and a heap, and perform basic operations like insert, search, and delete on it.
Replace each array element by its corresponding rank
Given an array of distinct integers, replace each array element by its corresponding rank in the array. The minimum array element has the rank 1; the second minimum element has a rank of 2, and so on…
Efficiently merge `k` sorted linked lists
In the previous post, we have discussed how to merge two sorted linked lists into one list. This post will merge k sorted linked lists into a single list efficiently.
Convert min heap to max heap in linear time
Given an array representing a min-heap, convert it into a max-heap. The conversion should be done in-place and in linear time.
Merge `M` sorted lists of variable length
Given M sorted lists of variable length, print them efficiently in sorted order.
Introsort Algorithm – Overview and C++ Implementation
Introsort is an efficient in-place sorting algorithm, which usually beats all other sorting algorithms in terms of performance. Due to its high performance, it is used in several standard library sort functions.
Huffman Coding Compression Algorithm
Huffman coding (also known as Huffman Encoding) is an algorithm for doing data compression, and it forms the basic idea behind file compression. This post talks about the fixed-length and variable-length encoding, uniquely decodable codes, prefix rules, and Huffman Tree construction.