Heap_size in heap_sort
Я читаю «Введение в алгоритмы» Кормена и пытаюсь реализовать сортировку кучи, и есть одна вещь, которую я постоянно не понимаю: как мы вычисляем heap_size для данного массива?
Мой учебник говорит
Массив A, представляющий кучу, представляет собой объект с двумя атрибутами:
A.length, которое (как обычно) дает количество элементов в массиве,
и A.heap-size, который представляет, сколько элементов в куче
хранится в массиве A. То есть, хотя A [1 .. A.length] может содержать
числа, только элементы в A [1..A.heap-size], где 0 <= A.heap-size <знак равно
Длина, допустимые элементы кучи.
Если я реализую массив как std::vector<T> Arrтогда его размер будет Arr.size, но каким бы он ни был, heap_size в настоящее время мне недоступен.
Решение
Размер кучи должен быть отдельно хранимой переменной, которой вы управляете сами.
Всякий раз, когда вы удаляете из кучи или добавляете ее, вы должны уменьшать или увеличивать значение соответствующим образом.
В C ++, используя vectorвы можете использовать sizeпоскольку базовое представление представляет собой массив, который по крайней мере такой же большой, как размер вектора, и он гарантированно останется таким же размером, если вы вызовете resize с меньшим размером. (Таким образом, базовый массив будет размером массива, а векторным размером будет размер кучи).
Другие решения
Других решений пока нет …