Hard Algorithms

Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure to build a max-heap and then repeatedly extracts the maximum element. With a guaranteed O(n log n) time complexity regardless of input data and O(1) auxiliary space, it combines many advantages of insertion sort and merge sort. While not stable and slightly slower than quick sort in practice, heap sort provides reliable performance without the risk of worst-case scenarios, making it valuable for systems requiring consistent performance.

Dijkstra's Algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge weights. It works by maintaining a set of vertices whose shortest distance from the source is already known and repeatedly selecting the vertex with the minimum distance value, updating the distance values of its adjacent vertices. Dijkstra's algorithm is widely used in network routing protocols and as a subroutine in other graph algorithms.

Bellman-Ford computes shortest paths from a single source to every other vertex in a weighted graph, even when some edge weights are negative. It works by relaxing all edges repeatedly: after V-1 passes the distances are guaranteed correct if no negative cycle is reachable from the source. Slower than Dijkstra at O(V·E) but more general — and a single extra pass detects negative cycles. Used in distance-vector routing protocols and as the inner loop of Johnson's algorithm.

Edit distance — also called Levenshtein distance — measures the minimum number of single-character insertions, deletions, or substitutions needed to turn one string into another. The classic dynamic-programming solution fills an (m+1)×(n+1) table where dp[i][j] is the cost to transform the first i characters of one string into the first j of the other. Each cell depends only on its top, left, and top-left neighbours, so the table fills row-by-row in O(m·n). The traceback through the dependencies reconstructs an optimal edit script. Variants underpin spell-checkers, DNA alignment, and diff tools.