Как лучше всего описать алгоритмы TreeSort и HeapSort?

Question

Как лучше всего описать алгоритмы TreeSort и HeapSort?

Я прочитал вики-страницу и другие ответы на Stackru. Надеясь, кто-то может объяснить, что делают эти два алгоритма.

Спасибо

2

tree binary-tree binary-search-tree heapsort treesort

Источник

user5480929 02 ноя '16 в 13:42

1 ответ

Решение

Другие вопросы по тегам tree binary-tree binary-search-tree heapsort treesort

user1465553 02 ноя '16 в 14:03 2016-11-02 14:03 · Accepted Answer · 2016-11-02 14:03

Treesort использует обход по порядку, выполняемый через двоичное дерево поиска (BST). Строительство BST из n предметы берут O(n * depth of tree) = O(n * log n) время.

Heapsort работает по логике, согласно которой самый большой элемент хранится в корне кучи. Строим кучу n предметы берут O(n * each_heapify_TimeComplexity) = O(n * log n) время.

Для винтовой древовидной структуры Treesort TC будет O(n^2), Хотя Heapsort отличается в этом отношении, так как он сохраняет глубину до минимально возможного значения, формируя себя как полное двоичное дерево.