KO
std::make_heap всегда делает полную перебалансировку.
Size: a a a
2020 July 22
CD
интрузивный хип - это такой хип, который внутри ноды содержит её position in the heap, и во время sift_up/sift_down обновляет эту позицию.
а, а чем set просядет от этой структуры?
CD
ну чутка дисбаланс больше, раза в 1.5
KO
причём тут дисбаланс, у Set стоимость операции log(N), а у heap - константа
CD
причём тут дисбаланс, у Set стоимость операции log(N), а у heap - константа
какая стоимость операции? апдейт логарифм, запрос середины - константа
KO
для того чтобы обновить позицию одного элемента, его надо будет удалить и вставить заново. то есть два логарифма.
CD
для того чтобы обновить позицию одного элемента, его надо будет удалить и вставить заново. то есть два логарифма.
а в хипе вам надо будет тащить его до корня, то есть один логарифм, это все еще константа
KO
я не распарсил.
CD
я не распарсил.
ну изменение ключа в хипе это логарифм, разумеется
KO
нет
CD
что значит нет?
KO
не логарифм
CD
не логарифм
я вам за линию массив отсортирую прямо сейчас
CD
там линейное построение + линейное число изменений ключа
KO
не надо, просто прочитайте как это работает. частичная перебалансировка кучи -константа
CD
не надо, просто прочитайте как это работает. частичная перебалансировка кучи -константа
make_heap линия, изменение одного элемента - логарифм
KO
спасибо большое за ответ.
CD
спасибо большое за ответ.
Ну проверьте. Хипсорт требует один раз построить хипу, после чего N раз поменять значение ключа в корне.
CD
Построение за O(N), откуда взялся N * log N?
CD
Там получается амортизация, если изменять все элементы, потому что никакой элемент не пытается всплывать, а средний путь вниз О(1).