I'm doing an assignment for school, where we have to implement different functions for a heap. Using Google Test to test the program, it gives me the following error.
My code is as follows, as a template of the class MinHeap:
void insert(const T& x)
{
heap.push_back(x);
percolateUp(heap.size());
}
void remove()
{
heap[0] = heap.back();
heap.pop_back();
percolateDown(0);
}
bool isEmpty() const
{
return heap.empty();
}
T peek() const
{
if (heap.empty())
{
throw exception("Heap is empty");
}
return heap[0];
}
private:
void percolateUp(size_t i)
{
if (i != 0)
{
if (heap[i] < heap[parent(i)])
{
swap(i, parent(i));
percolateUp(parent(i));
}
}
}
void percolateDown(size_t i)
{
if (!heap.empty())
{
if (heap[i] > heap[smallest(i)])
{
swap(i, smallest(i));
percolateDown(smallest(i));
}
}
}
size_t smallest(size_t i) const // returns index of smallest of i and its parents
{
size_t small = i;
if (left(i) < heap.size() &&
heap[i]> heap[left(i)])
small = left(i);
if (right(i) < heap.size() &&
heap[i]> heap[right(i)] &&
heap[right(i)]< heap[left(i)])
small = right(i);
return small;
}
void swap(size_t x, size_t y)
{
T temp = heap[x];
heap[x] = heap[y];
heap[y] = temp;
}
size_t parent(size_t i) const { return (i - 1) / 2; }
size_t left(size_t i) const { return 2 * i + 1; }
size_t right(size_t i) const { return 2 * i + 2; }
vector<T> heap;
};
I'm then testing the code using a Google Test .cpp file provided by my professor.
Aucun commentaire:
Enregistrer un commentaire