創建最大堆的時間複雜度O（n）

Question

創建最大堆O（n）的時間複雜度如何？它是僅在O（i）中與其父代進行比較還是O（log n）？

Answer 1

a。當我們使用冒泡方法進行排序時，複雜度爲O（n）。

這裏的想法是通過盲目地將元素插入到數組中，然後開始使用自下而上的方法來糾正/交換優勢違規而構建的。 優點：我們有n/2個葉節點，它們不需要任何氣泡，因爲它們自動遵守優勢。然後，我們轉向內部父母，並將其與孩子進行比較。如果違規存在，則交換/冒泡。然後移到較高父母等 即使是內部（父母）節點也需要對應其所在級別的高度進行交換。 n/2是葉子。 （最大高度：lg n）

求和從0到lg n：n/4在高度1，n/8在2的高度...導致堆積的成本達到以下等式： （n/2^h + 1）h

其中歸結爲約。 2n

因此時間複雜度爲O（n）。

b。比較只發生在給定家長級別的兒童身上。

希望它回答你的問題