Реализации двоичной кучи. В чём не корректен код?

Question

[muller92]

есть задание по построение кучи пытался по разному дохожу до 3 теста й потом ведают не правильный ответ. проверил на разные условие но у меня всё в порядке. если кто может подскажите пожалуйста

Задача на программирование. Данная задача состоит в реализации двоичной кучи. В первой строке ввода задаётся число n (1≤n≤105), далее n строк вида Insert X, где X — натуральное число, не превосходящее 109, или Extract. Первая операция должна добавлять в кучу число X, вторая должна извлекать максимум из кучи и выводить его в очередной строке вывода.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

class SimpleBinaryHeap {

	vector<int> heap_data;

public:

	void add(int value)
	{
		heap_data.push_back(value);
		int i = heap_data.size() - 1;
		int parent = (i - 1) / 2;

		while (i > 0 && heap_data[parent] < heap_data[i])
		{
			int temp = heap_data[i];
			heap_data[i] = heap_data[parent];
			heap_data[parent] = temp;

			i = parent;
			parent = (i - 1) / 2;
		}

	}
	void heapify(int i){
		int leftChild;
		int rightChild;
		int largestChild;

		for (;;)
		{
			leftChild = 2 * i + 1;
			rightChild = 2 * i + 2;
			largestChild = i;

			if (leftChild < heap_data.size() && heap_data[leftChild] > heap_data[largestChild])
			{
				largestChild = leftChild;
			}

			if (rightChild < heap_data.size() && heap_data[rightChild] > heap_data[largestChild])
			{
				largestChild = rightChild;
			}

			if (largestChild == i)
			{
				break;
			}

			int temp = heap_data[i];
			heap_data[i] = heap_data[largestChild];
			heap_data[largestChild] = temp;
			i = largestChild;
		}

	}

	int extract() {

		int res = heap_data[0];
		heap_data[0] = heap_data[heap_data.size() - 1];

		int index = 0;

		for (int i = heap_data.size() / 2; i >= 0; i--)
		{
			heapify(i);
		}
		heap_data.pop_back();

		return res;

	}
	int heapSort()
	{

		for (int i = heap_data.size() - 1; i >= 0; i--)
		{

			heapify(0);
			return extract();
		}
	}
};

int main() {

	SimpleBinaryHeap bh;

	string command;
	const char* com_insert = "Insert";
	const char* com_extract = "Extract";

	short num;
	cin >> num;

	for (short int i = 0; i < num; i++) {

		cin >> command;
		if (command == com_insert) {
			int value;
			cin >> value;
			bh.add(value);
		}
		if (command == com_extract) {
			cout << bh.heapSort() << endl;
		}

	}

	return 0;
}

Answer 1

[throughtheether]

if (command == com_extract) {
			cout << bh.heapSort() << endl;
		}

Вам надо извлечь корневое значение, восстановить свойство кучи и вернуть предварительно извлеченное значение. Мне не вполне ясно, что вы делаете:

int heapSort()
	{

		for (int i = heap_data.size() - 1; i >= 0; i--)
		{

			heapify(0);
			return extract();
		}
	}

Почему, например, return в цикле?
Если я правильно понял, то вам надо строку cout << bh.heapSort() << endl; заменить на cout << bh.extract() << endl;

Comments

[muller92]

делал и так но на 3 тесты выдает не правильный ответ. return для вывода числа

[evnuh]

@muller92 return - выход из функции, соответственно у вас цикл здесь бесполезный, сработает только первая интерация - дальше он выйдет из функции напрочь.

[muller92]

надо было поменять тип на int

[throughtheether]

надо было поменять тип на int

В первой строке ввода задаётся число n (1≤n≤105)

Если вместо 105 имелось в виду 10^5, то да. Но это не отменяет того, что код функции heapsort(), мягко говоря, немного странный.