用c++语言编写一个程序输入N个元素，并将它们一个一个地插入到一个最小堆中。以线性时间建立一个堆。 比较两个算法对于已排序、反序以及随机输入的运行时间。

在C++中，我们可以使用标准库`<algorithm>`中的`make_heap`函数来在线性时间内构建一个最小堆。首先，我们需要定义一个结构体或类来存储数据并实现小于操作。这里我将以整数为例：

#include <iostream>
#include <vector>
#include <queue>
#include <ctime>

struct Compare {
    bool operator()(int a, int b) { return a < b; } // 最小堆，a总是比b小
};

void insert_sorted(int N, std::vector<int>& nums) {
    std::priority_queue<int, std::vector<int>, Compare> minHeap;
    for (int i = 0; i < N; ++i) {
        minHeap.push(nums[i]);
    }
}

void insert_reversed(int N, std::vector<int>& nums) {
    std::priority_queue<int, std::vector<int>, Compare> minHeap;
    for (int i = N - 1; i >= 0; --i) {
        minHeap.push(nums[i]);
    }
}

void insert_random(int N, std::vector<int>& nums) {
    std::priority_queue<int, std::vector<int>, Compare> minHeap;
    std::srand(std::time(0)); // 设置随机种子
    for (int i = 0; i < N; ++i) {
        minHeap.push(nums[i]); // 假设nums是一个预先填充了随机数的向量
    }
}

int main() {
    std::vector<int> nums(N); // 填充测试数据

    // 测试三种情况的时间
    auto start_sorted = std::chrono::high_resolution_clock::now();
    insert_sorted(N, nums);
    auto end_sorted = std::chrono::high_resolution_clock::now();

    auto start_reversed = std::chrono::high_resolution_clock::now();
    insert_reversed(N, nums);
    auto end_reversed = std::chrono::high_resolution_clock::now();

    auto start_random = std::chrono::high_resolution_clock::now();
    insert_random(N, nums);
    auto end_random = std::chrono::high_resolution_clock::now();

    double sorted_time = std::chrono::duration_cast<std::chrono::microseconds>(end_sorted - start_sorted).count();
    double reversed_time = std::chrono::duration_cast<std::chrono::microseconds>(end_reversed - start_reversed).count();
    double random_time = std::chrono::duration_cast<std::chrono::microseconds>(end_random - start_random).count();

    std::cout << "Sorted input time: " << sorted_time << " us\n";
    std::cout << "Reversed input time: " << reversed_time << " us\n";
    std::cout << "Random input time: " << random_time << " us\n";

    return 0;
}

在这个程序中，我们分别对已排序、反序和随机输入的情况进行了时间测量。一般来说，因为最小堆的特性，对于已排序的数组，插入过程几乎是常数时间；而对于反序和随机输入，由于需要调整堆结构，时间可能会增加。