爲什麼is_heap（）不驗證由我創建堆，雖然它是有效的概念

Question

我用C++寫了堆實現後的今天我才知道，有在C++ 11的內置功能，可以使任何範圍基礎容器堆。

因此，出於好奇，我使用我自己的實現將一個向量轉換爲堆，並使用函數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>()); 
} 

輸出：

1