Advanced Data Structures

Beyond Arrays and Lists

You've already worked with fundamental data structures like arrays, vectors, and linked lists. They are the building blocks of programming. But as problems get more complex and datasets grow larger, we need more specialized tools. This is where advanced data structures come in. They offer clever ways to organize data to perform specific tasks—like finding the highest-priority item or searching for data in massive collections—with incredible speed.

Heaps and Priority Queues

Imagine an emergency room. Patients aren't treated in the order they arrive, but by the severity of their condition. A simple queue won't work. This is the perfect job for a priority queue, an abstract data type where every item has a priority, and the highest-priority item is always accessible.

The most common way to build a priority queue is with a heap. A heap is a special kind of binary tree that has two key properties:

Shape Property: It must be a complete binary tree. This means every level is full, except possibly the last one, which is filled from left to right.
Heap Property: In a max-heap, every parent node is greater than or equal to its children. In a min-heap, every parent is less than or equal to its children.

This structure guarantees that the root node is always the maximum (in a max-heap) or minimum (in a min-heap) element. Finding this top element is instant ( $O(1)$ ), while adding or removing it is very fast ( $O(\log n)$ ).

In C++, the Standard Template Library (STL) provides std::priority_queue, a container that does all the heap management for you.

#include <iostream>
#include <queue> // For std::priority_queue
#include <vector>

int main() {
    // By default, std::priority_queue is a max-heap.
    std::priority_queue<int> tasks;

    // Add tasks with different priorities
    tasks.push(30);  // Medium priority
    tasks.push(100); // High priority
    tasks.push(10);  // Low priority

    std::cout << "Processing tasks by priority:\n";
    while (!tasks.empty()) {
        // .top() accesses the highest priority element
        std::cout << tasks.top() << std::endl; 
        // .pop() removes it
        tasks.pop();
    }
    return 0;
}

Keeping Trees Balanced

Binary Search Trees (BSTs) are great for fast lookups, insertions, and deletions, all averaging $O(\log n)$ time. But they have a major weakness: if you insert data that's already sorted, the tree becomes unbalanced and degenerates into a linked list. Performance drops to a dismal $O(n)$ .

To solve this, we use self-balancing binary search trees. These trees automatically adjust their structure after insertions or deletions to stay balanced, preserving their $O(\log n)$ performance in all cases. Two popular types are AVL trees and Red-Black trees.

Feature	AVL Tree	Red-Black Tree
Balancing	Stricter. Height difference between left/right subtrees cannot be more than 1.	More relaxed. Uses node colors (red/black) and rules to ensure no path is more than twice as long as any other.
Insertions	Can require more rotations, making them slightly slower.	Faster insertions, as they are less strictly balanced and require fewer rotations on average.
Lookups	Faster lookups because the tree is more rigidly balanced.	Slightly slower lookups than AVL trees, but still guaranteed $O(\log n)$ .
Use Case	Best for lookup-heavy applications where insertions are infrequent.	A better general-purpose choice. Used in `std::map` and `std::set` in C++.

You rarely need to implement these from scratch. The key is to know they exist and understand the trade-offs. When you use std::map or std::set in C++, you are already using a highly-optimized Red-Black tree under the hood.

Hash Tables

What if you could find an element in a collection instantly, without searching? That's the promise of a hash table. It uses a special hash function to convert a key (like a username string) into an index in an array. This lets you access the corresponding value directly.

For example, a hash function might take the string "alice" and compute the index 42. We can then store Alice's data at array[42]. This gives us an average lookup time of $O(1)$ —blazing fast.

But what happens if the hash function computes the same index for two different keys? This is called a collision. All hash tables need a strategy to resolve collisions. The two most common methods are:

Separate Chaining: Each array slot holds a pointer to a linked list (or another data structure). When a collision occurs, the new element is just added to the list at that index.
Open Addressing: If an index is already taken, the algorithm probes for the next available slot according to a fixed sequence. Simple linear probing just checks the next slot (index + 1, index + 2, etc.), but more complex methods exist.

C++ provides std::unordered_map and std::unordered_set, which are implementations of hash tables. They are extremely useful when you need fast key-value lookups and don't care about keeping the elements in a sorted order.

Quiz Questions 1/5

Which of the following scenarios is the most appropriate use case for a priority queue?

Quiz Questions 2/5

In a max-heap, every parent node's value must be greater than or equal to its children's values.

Choosing the right data structure is about understanding these trade-offs. Each has strengths and weaknesses, and picking the right one is a key skill for writing efficient, scalable code.

Intermediate C++ Data Structures and Algorithms