#pragma once
#include <stddef.h>
#include <stdint.h>
#include <vector>
#include <functional>

// Task priority comparator
// Higher priority first, then earlier created_at
template<typename T>
struct PriorityComparator {
    std::function<int64_t(const T&)> get_priority;
    std::function<int64_t(const T&)> get_created_at;
    
    bool operator()(size_t a, size_t b, const std::vector<T>& items) const {
        int64_t pa = get_priority(items[a]);
        int64_t pb = get_priority(items[b]);
        if (pa != pb) {
            return pa < pb;  // Max-heap: higher priority first
        }
        return get_created_at(items[a]) > get_created_at(items[b]);  // Earlier first
    }
};

// Binary heap for priority queue
// Uses indices into external storage for indirection
template<typename T, typename Comparator>
class BinaryHeap {
    std::vector<size_t> heap_;  // Indices into items_
    const std::vector<T>& items_;
    Comparator comp_;
    
    void sift_up(size_t idx);
    void sift_down(size_t idx);
    
public:
    BinaryHeap(const std::vector<T>& items, Comparator comp);
    
    // Build heap from unsorted indices
    void build(const std::vector<size_t>& indices);
    
    // Pop highest priority item
    size_t pop();
    
    // Peek at highest priority item without removing
    size_t peek() const { return heap_.empty() ? SIZE_MAX : heap_.front(); }
    
    // Get all items as sorted vector (highest priority first)
    std::vector<size_t> sorted() const;
    
    bool empty() const { return heap_.empty(); }
    size_t size() const { return heap_.size(); }
    
    void clear() { heap_.clear(); }
};
