malloc.c:2379: sysmalloc: Assertion... failed

Question

Im currently writing a program that uses Heap class, to find the max value in part of array (size of part is k), which is moving in array, until reaches the end. It crushes on dataset: 3 1 2 3 1 with misstake: malloc.c:2379: sysmalloc: Assertion `(old_top == initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= MINSIZE && prev_inuse (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0)' failed. It crushes when it tryes to cout the temp.value variable. If i cooment it, everything works just fine

Here is my code:

#include <iostream>
#include <cstring>
#include <cassert>

#define DEFAULT_GROW 2

template<class T>
class IsLess {
public:
    bool operator()(const T& lhs, const T& rhs) const {
        return lhs < rhs;
    }
};

template<class T>
struct Node {
    T value;
    size_t index;
};


template <class T, class H = IsLess<T>>
class Heap {
public:
    Heap();
    Heap(const T* arr, size_t dataSize, H func = IsLess<T>());
    Heap(const Heap&) = delete;
    Heap(Heap&&) = delete;
    Heap operator = (const Heap&) = delete;
    Heap operator = (Heap&&) = delete;
    ~Heap();
    bool IsEmpty();
    void Insert(const T &k);
    Node<T> ExtractMax();
    Node<T> ExtractMaxByIndex(const size_t &i, const size_t &k);
    void InsertNode(const Node<T> &);

private:
    void Grow();
    void BuildHeap();
    void SiftDown(const int &i);
    void SiftUp(int i);
    size_t capacity;
    size_t size;
    Node<T>* data;
    H comparator;
};

template<class T, class H>
Heap<T, H>::Heap():
capacity(0),
size(0),
data(nullptr),
comparator(IsLess<T>())
{}

template<class T, class H>
Heap<T, H>::Heap(const T* arr, size_t dataSize, H func) {
    assert(arr != nullptr);
    assert(dataSize > 0);
    data = new Node<T>[dataSize];
    capacity = dataSize;
    size = dataSize;
    comparator = func;
    // std::memcpy(data->value, arr, dataSize * sizeof(T) - 1);
    for (size_t i = 0; i < dataSize; ++i) {
        data[i].value = arr[i];
        data[i].index = i;
    }
    BuildHeap();
}

template<class T, class H>
Heap<T, H>::~Heap() {
    delete[] data;
}

template<class T, class H>
void Heap<T, H>::Grow() {
    if (capacity == 0) {
        data = new Node<T>[++capacity];
        return;
    }
    if (size < capacity) {
        return;
    }
    capacity *= DEFAULT_GROW;
    Node<T> *buf = new Node<T>[capacity];
    std::memcpy(buf, data, sizeof(Node<T>) * size - 1);
    delete[] data;
    data = buf;
}

template<class T, class H>
void Heap<T, H>::SiftDown(const int &i) {
    size_t leftChild = i * 2 + 1;
    size_t rightChild = i * 2 + 2;
    size_t largest = i;
    if(leftChild < size
    && comparator(data[largest].value, data[leftChild].value)) {
        largest = leftChild;
    }
    if(rightChild < size
    && comparator(data[largest].value, data[rightChild].value)) {
        largest = rightChild;
    }
    if(largest != i) {
        std::swap(data[i], data[largest]);
        SiftDown(largest);
    }
}

template<class T, class H>
void Heap<T, H>::SiftUp(int i) {
    while(i > 0) {
        int parent = (i - 1) / 2;
        if(comparator(data[i].value, data[parent].value)) {
            return;
        }
        std::swap(data[i], data[parent]);
        i = parent;
    }
}

template<class T, class H>
void Heap<T, H>::BuildHeap() {
    for (int i = size / 2 - 1 ; i >= 0 ; --i) {
        SiftDown(i);
    }
}

template<class T, class H>
bool Heap<T, H>::IsEmpty() {
    return size == 0;
}

template<class T, class H>
void Heap<T, H>::Insert(const T &k) {
    if (IsEmpty() || size == capacity) {
        Grow();
    }
    data[size].value = k;
    data[size].index = size;
    SiftUp(size++);
}

template<class T, class H>
Node<T> Heap<T, H>::ExtractMax() {
    assert(!IsEmpty());
    Node<T> result = data[0];
    data[0] = data[--size];
    if (!IsEmpty()) {
        SiftDown(0);
    }
    return result;
}

template<class T, class H>
void Heap<T, H>::InsertNode(const Node<T> &node) {
    if (IsEmpty() || size == capacity) {
        Grow();
    }
    data[size] = node;
    SiftUp(size++);
}

template<class T, class H>
Node<T> Heap<T, H>::ExtractMaxByIndex(const size_t &i, const size_t &k) {
    assert(!IsEmpty());
    Node<T> result = {0, i + k + 1}; //  чтобы условие не выполнилось с 1 раза
    Node<T> *extracted = new Node<T>[k];
    size_t extractedIndex = 0;
    while(result.index < i || result.index > i + k - 1) {
        result = ExtractMax();
        extracted[extractedIndex++] = result;
    }
    for (size_t j = 0 ; j < extractedIndex ; ++j) {
        InsertNode(extracted[j]);
    }
    delete [] extracted;
    return result;
}

void Answer (unsigned int *arr, const size_t &n, const size_t &i, const size_t &k) {
    assert(arr != nullptr);
    Heap<unsigned> heap(arr, n);
    //size_t resSize = n - k + 1;

    Node<unsigned int> temp = heap.ExtractMaxByIndex(i, k);
    std::cout << temp.value << " ";  // This line causes the misstake
}

int main() {
    size_t n = 0;
    std::cin >> n;
    unsigned int *arr = new unsigned int[n];
    for (size_t i = 0; i < n; ++i) {
        std::cin >> arr[i];
    }
    size_t k = 0;
    std::cin >> k;
    for (size_t i = 0 ; i < 1 ; ++i) {
        Answer(arr, n, i, k);
    }
    delete[] arr;
    return 0;
}

Input: 
3
1 2 3
1

Output:
1 2 3

Answer 1

Your problem is in this part of code:

template<class T, class H>
Node<T> Heap<T, H>::ExtractMaxByIndex(const size_t& i, const size_t& k)
{
    assert(!IsEmpty());
    Node<T> result = { 0, i + k + 1 }; //  чтобы условие не выполнилось с 1 раза
    Node<T>* extracted = new Node<T>[k]; <- right here
    size_t extractedIndex = 0;
    while (result.index < i || result.index > i + k - 1)
    {
        result = ExtractMax();
        extracted[extractedIndex++] = result; <- and right here
    }
    for (size_t j = 0; j < extractedIndex; ++j)
    {
        InsertNode(extracted[j]);
    }
    delete[] extracted;
    return result;
}

First, you are allocating less memory than needed (in your sample, k is 1), then you try to assign a value in memory that is out of bounds of your allocated dynamic memory here:

extracted[extractedIndex++] = result;