为什么 is_heap() 不验证我创建的堆，尽管它在概念上是有效的

Question

我用 C++ 编写了堆实现，今天晚些时候我才知道，C++11 中有内置函数可以使任何基于运行ge 的容器成为堆。

所以出于好奇，我使用自己的实现将向量放入堆中，并使用了函数 make_heap()，然后对它们都使用了运行 is_heap()。

使用 make_heap() 制作的验证为 true，但我的没有，即使它在技术上是有效的。

下面是源代码和截图

头文件

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
using namespace std;

主要heapify函数

vector<int> heapify(vector<int> nums, string const & type) {
    int n = nums.size();
    for (int i = n - 1; i >= 0; i--) {
        int parent = floor((i-1)/2);

        if (parent >= 0) {
            if (type == "min") {
                if (nums[i] < nums[parent]) {
                    swap(nums[i], nums[parent]);
                }
            } else {
                if (nums[i] > nums[parent]) {
                    swap(nums[i], nums[parent]);
                }
            }
        }
    }
    return nums;
}

构建堆的函数

vector<int> buildHeap(vector<int> const & nums, string const & type) {
    vector<int> heap;
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        heap.push_back(nums[i]);
        if (!heap.empty()) {
            heap = heapify(heap, type);
        }
    }
    return heap;
}

删除最上面的元素

int getTop(vector<int> & nums, string const & type) {
    int n = nums.size();
    if (n < 0) {
        throw string("Size of array is less than 0");
    } else {
        int minElem = nums[0];
        swap(nums[0], nums[n-1]);
        nums.pop_back();
        nums = heapify(nums, type);
        return minElem;
    }
}

主要功能

int main()
{
    vector<int> nums = {45, 56, 78, 89, 21, 38, 6, 67, 112, 45, 3, 1};
    vector<int> heap = buildHeap(nums, "min");
    for (int num : heap) {
        cout << num << " ";
    }
    cout << "\n";

    cout << std::is_heap(nums.begin(), nums.end(), greater<int>()) << "\n";
    make_heap(nums.begin(), nums.end(), greater<int>());
    for (int num : nums) {
        cout << num << " ";
    }
    cout << "\n";
    cout << std::is_heap(nums.begin(), nums.end(), greater<int>()) << "\n";
    return 0;
}

控制台输出截图和 https://www.cs.usfca.edu/~galles/visualization/Heap.html

验证

Answer 1

你不运行第一个is_heap在你的堆上，你运行它在原始向量上。那个明显不是一堆

此行未检查您的堆：

cout << std::is_heap(nums.begin(), nums.end(), greater<int>()) << "\n";

你的堆变量叫做heap:

cout << std::is_heap(heap.begin(), heap.end(), greater<int>()) << "\n";

Answer 2

您的实现使堆成为原始序列的副本。因此您需要验证副本 (heap)，而不是原始序列 (nums)。

    cout << std::is_heap(heap.begin(), heap.end(), greater<int>()) << "\n";

你的序列是一个堆，here's proof:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    vector<int> vec = {1, 6, 3, 67, 45, 21, 38, 89, 112, 56, 45, 78};
    std::cout << is_heap(vec.begin(), vec.end(), greater<int>());
}

输出：

为什么 is_heap() 不验证我创建的堆，尽管它在概念上是有效的

Why is_heap() not validating the heap created by me though it is valid conceptually

c++

algorithm

heap

c++11