lundi 31 juillet 2017

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

I wrote a heap implementation in C++ and later today I came to know that, there are inbuilt functions in C++11 that can make any range based container a heap.

So out of curiosity I made a vector into heap using my own implementation and used the function make_heap() and then ran is_heap() on both of them.

The one made using make_heap() verified to true, but mine did not, even though it is technically valid.

Source code and screenshots below

Main heapify function

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;
}

Function that builds the heap

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;
}

Remove the top most element

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;
    }
}

Main function

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;
}

Screenshots of output on console and verification on http://ift.tt/1JBWNjW

Output Console

Output verification

Aucun commentaire:

Enregistrer un commentaire