Я пытаюсь удалить максимум, поменяв местами первый и последний элемент вектора, а затем используя pop_back. Когда я удаляю max, я вывожу max, но процесс переупорядочивания работает неправильно, и я не могу понять, почему.
Я пытался изменить способ тестирования несколько раз, и результаты не меняются. Может ли кто-нибудь увидеть, где я ошибся?
#include <vector>
#include <string>
class Heap
{
public:
void insert(int data)
{
int parent = 0;
heap.push_back(data);
current = heap.size() - 1;
parent = (current - 1) / 2;
if (heap.size() > 1)
{
while (heap.at(parent) < heap.at(current))
{
if (heap.at(current) > heap.at(parent))
{
std::swap(heap.at(parent), heap.at(current));
current = parent;
parent = (parent - 1) / 2;
}
}
}
// for(int i = 0; i < heap.size(); i++)
// {
// std::cout << heap.at(i) << std::endl;
// }
// std::cout << std::endl;
}
void remove_max()
{
if (!heap.empty())
{
if (heap.size() == 1)
{
heap.pop_back();
return;
}
std::swap(heap.at(0), heap.at(heap.size() - 1));
heap.pop_back();
int parent = heap.at(0);
int lchild = (parent * 2) + 1;
int rchild = (parent * 2) + 2;
// while(lchild < heap.size() && rchild < heap.size())
// {
// if (heap.at(lchild) < heap.at(rchild))
// {
// std::swap(heap.at(parent), heap.at(rchild));
// parent = rchild;
// }
// else
// {
// std::swap(heap.at(parent), heap.at(lchild));
// parent = rchild;
// }
// lchild = (lchild * 2) + 1;
// rchild = (rchild * 2) + 2;
// }
if (lchild < rchild)
{
while (parent > lchild)
{
std::swap(heap.at(parent), heap.at(lchild));
lchild = (lchild * 2) + 1;
parent = (rchild - 1) / 2;
}
}
else
{
while (parent > rchild)
{
std::swap(heap.at(parent), heap.at(rchild));
rchild = (rchild * 2) + 2;
parent = (rchild - 1) / 2;
}
}
}
// for(int i = 0; i < heap.size(); i++)
// {
// std::cout << heap.at(i) << std::endl;
// }
// std::cout << std::endl;
return;
}
int max()
{
return heap.at(0);
}
bool empty()
{
return heap.empty();
}
private:
std::vector<int> heap;
int current = 0;
};
int main()
{
// TODO: implement!
Heap myHeap;
std::string command;
int data;
do
{
std::cin >> command;
if (command == "add")
{
std::cin >> data;
myHeap.insert(data);
}
else if (command == "run")
{
std::cout << myHeap.max() << std::endl;
myHeap.remove_max();
}
else if (command == "exit")
{
while (!myHeap.empty())
{
std::cout << myHeap.max() << std::endl;
myHeap.remove_max();
}
}
} while (command != "exit");
return 0;
}
Ваша математика совершенно неверна. Вы путаете сохраненные значения с расчетами индекса. В некоторых местах вы вычисляете значения, умножая индексы, в других вы вычисляете индексы, умножая сохраненные значения. Это никогда не сработает.
void remove_max()
{
if (heap.empty())
return;
std::swap(heap.at(0), heap.at(heap.size() - 1));
heap.pop_back();
size_t parent = 0;
do
{
// get first child slot
size_t child = 2*parent + 1;
if (child < heap.size())
{
// calculate right-child index.
size_t rchild = 2*(parent+1);
if (rchild < heap.size() && heap[rchild] > heap[child])
child = rchild;
// got the child slot. now compare.
if (heap[child] > heap[parent])
{
std::swap(heap[child], heap[parent]);
parent = child;
}
else
{
// parent larger than children. stop here.
break;
}
}
else
{
// reached a node with no children
break;
}
} while (true);
}
Извините за поздний ответ, но большое спасибо. Я работал над этим в течение нескольких дней и не мог понять, что делать.