时间戳

首页 > 解决方案 > 构建堆的时间复杂度

c++ - 构建堆的时间复杂度

问题描述

我试图了解 C++ STL priority_queue 用于构建堆的时间复杂度。对于构建堆，时间复杂度应为 O(n)。假设我们有一个包含 n 个元素的向量，并且我们想从该向量构建一个最大堆。代码将是这样的 -

vector<int> vec{3,4,5,1,2};
priority_queue<int> pq;

for (auto v : vec) {
pq.push(v);
}

推送操作需要 O(log n) 时间。在我看来，它是 O(nlogn) 时间复杂度。但是上面的代码片段只是第一次从向量中构建了一个堆。对于上述情况，即构建堆，复杂性如何为 O(n)。

编辑：如果上面的代码片段是 O(nlogn)，那么我想知道在 O(n) 中使用 priority_queue c++ stl 构建堆的代码。

标签： c++data-structuresstlheappriority-queue

解决方案

考虑这个用于构建输入数组 A 的堆的算法。

BUILD-HEAP(A) 
    heapsize := size(A); 
    for i := floor(heapsize/2) downto 1 
        do HEAPIFY(A, i); 
    end for 
END

这个上限O(nlg(n))虽然是正确的，但不是渐近紧的。

我们可以通过观察 Heapify 的运行时间取决于树 'h' 的高度（等于 lg(n)，其中 n 是节点数）和大多数子树的高度来得出更严格的界限小的。

我们可以通过观察 Heapify 的运行时间取决于树 'h' 的高度（等于 lg(n)，其中 n 是节点数）和大多数子树的高度来得出更严格的界限小的。

请参阅此链接，以获得完整的解释和数学证明。

推荐阅读