The heap (priority queue) is a complete binary tree maintaining the heap property. Min-heaps support O(log n) insert and extract-min, with O(1) peek. Python's heapq module implements min-heap efficiently, with max-heap simulated by negating values. Heaps power algorithms like Dijkstra's shortest path, top-k problems, Kth largest element, and median maintenance. Heap Sort builds a max-heap and repeatedly extracts the maximum for an in-place O(n log n) sort.
Union-Find (Disjoint Set Union) tracks elements partitioned into disjoint sets, supporting union and find operations in nearly O(1) amortized time using path compression and union by rank. It solves problems like finding connected components, detecting cycles in undirected graphs (Redundant Connection), merging accounts sharing emails, and implementing Kruskal's MST algorithm. The data structure elegantly reduces many graph problems to tracking component membership.
Specialized structures address specific query patterns. The Sparse Table precomputes answers for power-of-2 ranges, enabling O(1) idempotent queries like range minimum after O(n log n) preprocessing. Sqrt Decomposition divides arrays into √n-sized blocks, achieving O(√n) queries. The Line Sweep technique processes sorted events for problems like interval union length and platform counting. More exotic structures include the Bloom Filter (probabilistic set membership), Skip List (probabilistic balanced BST), Treap (randomized BST combining tree and heap properties), and Persistent Segment Tree (preserving historical versions with O(log n) new nodes per update).