Designing Custom Heaps for Competitive Programming

Introduction

Standard binary heaps are powerful, but competitive programming often demands specialized heap variants. Understanding when and how to implement d-ary heaps, Fibonacci heaps, and custom priority structures can be the difference between TLE and AC.

This guide explores advanced heap techniques that go beyond priority_queue, showing you how to design optimal solutions for complex problems.

Beyond Binary Heaps

Why Custom Heaps Matter

Standard heaps have limitations: - Binary heaps: Fixed branching factor - STL priority_queue: Limited customization - Performance bottlenecks in specific scenarios

Custom heaps solve these issues with tailored designs.

D-ary Heaps Implementation

D-ary heaps use d children per node instead of 2, offering better performance for certain operations.

Core Implementation

template
class DAryHeap {
private:
    vector heap;
    
    int parent(int i) { return (i - 1) / D; }
    int child(int i, int k) { return D * i + k + 1; }
    
    void heapifyUp(int i) {
        while (i > 0 && heap[i] < heap[parent(i)]) {
            swap(heap[i], heap[parent(i)]);
            i = parent(i);
        }
    }
    
    void heapifyDown(int i) {
        while (true) {
            int minChild = i;
            
            for (int k = 0; k < D; k++) {
                int c = child(i, k);
                if (c < heap.size() && heap[c] < heap[minChild]) {
                    minChild = c;
                }
            }
            
            if (minChild == i) break;
            swap(heap[i], heap[minChild]);
            i = minChild;
        }
    }
public:
    void push(const T& val) {
        heap.push_back(val);
        heapifyUp(heap.size() - 1);
    }
    
    T pop() {
        T result = heap[0];
        heap[0] = heap.back();
        heap.pop_back();
        if (!heap.empty()) heapifyDown(0);
        return result;
    }
    
    bool empty() const { return heap.empty(); }
    T top() const { return heap[0]; }
};

Performance Analysis

Advanced Custom Comparators

Multi-Criteria Priority Queue

struct Task {
    int priority;
    int deadline;
    int id;
    
    // Custom comparison for complex priority logic
    bool operator<(const Task& other) const {
        if (priority != other.priority) 
            return priority > other.priority; // Higher priority first
        if (deadline != other.deadline)
            return deadline > other.deadline; // Earlier deadline first
        return id > other.id; // Lower ID first (tie-breaker)
    }
};
// Usage in competitive programming
priority_queue taskQueue;
taskQueue.push({5, 100, 1});
taskQueue.push({5, 90, 2});  // This will be processed first (earlier deadline)

Dynamic Priority Updates

template
class UpdatableHeap {
private:
    vector heap;
    unordered_map idToIndex; // ID to heap index mapping
    
public:
    void updatePriority(int id, T newValue) {
        if (idToIndex.find(id) == idToIndex.end()) return;
        
        int index = idToIndex[id];
        T oldValue = heap[index];
        heap[index] = newValue;
        
        if (newValue < oldValue) {
            heapifyUp(index);
        } else {
            heapifyDown(index);
        }
    }
    
    // Dijkstra's algorithm with heap updates
    vector dijkstra(vector>>& graph, int start) {
        int n = graph.size();
        vector dist(n, INT_MAX);
        UpdatableHeap> pq; // {distance, node}
        
        dist[start] = 0;
        pq.push({0, start});
        
        while (!pq.empty()) {
            auto [d, u] = pq.pop();
            if (d > dist[u]) continue;
            
            for (auto [v, w] : graph[u]) {
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.updatePriority(v, {dist[v], v});
                }
            }
        }
        
        return dist;
    }
};

Fibonacci Heaps for Advanced Algorithms

Fibonacci heaps excel in algorithms requiring frequent decrease-key operations.

Key Operations

class FibonacciHeap {
    struct Node {
        int key, degree;
        bool marked;
        Node* parent;
        Node* child;
        Node* left;
        Node* right;
        
        Node(int k) : key(k), degree(0), marked(false), 
                      parent(nullptr), child(nullptr) {
            left = right = this;
        }
    };
    
    Node* minNode;
    int nodeCount;
    
public:
    FibonacciHeap() : minNode(nullptr), nodeCount(0) {}
    
    Node* insert(int key) {
        Node* node = new Node(key);
        
        if (!minNode) {
            minNode = node;
        } else {
            addToRootList(node);
            if (node->key < minNode->key) {
                minNode = node;
            }
        }
        
        nodeCount++;
        return node;
    }
    
    void decreaseKey(Node* node, int newKey) {
        if (newKey > node->key) return;
        
        node->key = newKey;
        Node* parent = node->parent;
        
        if (parent && node->key < parent->key) {
            cut(node, parent);
            cascadingCut(parent);
        }
        
        if (node->key < minNode->key) {
            minNode = node;
        }
    }
    
    // O(log n) amortized
    int extractMin() {
        Node* min = minNode;
        if (!min) return -1;
        
        // Add children to root list
        if (min->child) {
            Node* child = min->child;
            do {
                Node* next = child->right;
                addToRootList(child);
                child->parent = nullptr;
                child = next;
            } while (child != min->child);
        }
        
        removeFromRootList(min);
        
        if (min == min->right) {
            minNode = nullptr;
        } else {
            minNode = min->right;
            consolidate();
        }
        
        nodeCount--;
        int result = min->key;
        delete min;
        return result;
    }
};

Real-World Applications

1. Network Routing - Dijkstra Optimization

// Optimized for sparse graphs with frequent updates
class NetworkRouter {
    FibonacciHeap heap;
    vector nodes;
    
public:
    vector findShortestPaths(int source, vector>& graph) {
        int n = graph.size();
        vector dist(n, INT_MAX);
        nodes.resize(n);
        
        dist[source] = 0;
        nodes[source] = heap.insert(0);
        
        for (int i = 0; i < n; i++) {
            if (i != source) {
                nodes[i] = heap.insert(INT_MAX);
            }
        }
        
        while (!heap.empty()) {
            int u = heap.extractMin();
            
            for (Edge& e : graph[u]) {
                if (dist[u] + e.weight < dist[e.to]) {
                    dist[e.to] = dist[u] + e.weight;
                    heap.decreaseKey(nodes[e.to], dist[e.to]);
                }
            }
        }
        
        return dist;
    }
};

2. Task Scheduling with Dynamic Priorities

class DynamicTaskScheduler {
    DAryHeap taskHeap;
    unordered_map taskMap;
    
public:
    void addTask(int id, int priority, int deadline) {
        Task task = {priority, deadline, id};
        taskHeap.push(task);
        taskMap[id] = task;
    }
    
    void updateTaskPriority(int id, int newPriority) {
        if (taskMap.find(id) != taskMap.end()) {
            taskMap[id].priority = newPriority;
            // Rebuild heap (or use updatable heap)
            rebuildHeap();
        }
    }
    
    Task getNextTask() {
        while (!taskHeap.empty()) {
            Task task = taskHeap.top();
            taskHeap.pop();
            
            // Verify task is still valid
            if (taskMap[task.id].priority == task.priority) {
                taskMap.erase(task.id);
                return task;
            }
        }
        return {-1, -1, -1}; // No valid task
    }
};

Performance Optimization Techniques

Memory Pool for Frequent Allocations

template
class HeapWithPool {
    struct Node {
        T data;
        Node* left;
        Node* right;
        Node* parent;
    };
    
    static const int POOL_SIZE = 10000;
    Node pool[POOL_SIZE];
    int poolIndex = 0;
    
    Node* allocateNode(const T& data) {
        if (poolIndex < POOL_SIZE) {
            pool[poolIndex].data = data;
            return &pool[poolIndex++];
        }
        return new Node{data, nullptr, nullptr, nullptr};
    }
    
public:
    void reset() { poolIndex = 0; } // Fast reset for multiple test cases
};

Common Mistakes & Pitfalls

❌ Mistake 1: Incorrect D-ary Heap Indexing

// Wrong - off-by-one errors
int parent(int i) { return i / D; }        // Missing -1
int child(int i, int k) { return D * i + k; } // Missing +1
// Correct
int parent(int i) { return (i - 1) / D; }
int child(int i, int k) { return D * i + k + 1; }

❌ Mistake 2: Ignoring Amortized Complexity

// Don't assume all operations are O(log n)
// Fibonacci heap: insert O(1), decrease-key O(1) amortized
// But extract-min is O(log n)
// Plan your algorithm accordingly
for (int i = 0; i < n; i++) {
    heap.insert(i);           // O(1) each
    heap.decreaseKey(node, 0); // O(1) amortized
}
// Total: O(n), not O(n log n)

❌ Mistake 3: Memory Leaks in Custom Heaps

// Always implement proper cleanup
~FibonacciHeap() {
    clear();
}
void clear() {
    if (minNode) {
        clearNode(minNode);
        minNode = nullptr;
    }
}

Complexity Comparison

*Amortized complexity

Conclusion

Custom heaps unlock performance optimizations impossible with standard implementations. Choose the right variant based on your specific use case:

- D-ary heaps: When insert/decrease-key frequency >> extract-min - Fibonacci heaps: For graph algorithms with many decrease-key operations - Custom comparators: For complex priority logic

Master These Concepts: - Understand amortized analysis - Profile your specific use case - Consider memory vs. time trade-offs

Practice Problems: - Advanced Dijkstra Implementation - Task Scheduling Optimization - Network Flow with Custom Heaps

--- *Elevate your competitive programming skills with advanced data structures. Start practicing today!*