使用數組快捷方式形成二進制堆

Question

如果我們按照升序排列數組，那麼我們將得到二進制堆。這種優勢有什麼缺點嗎？如果是，那麼這是什麼原因呢？

Answer 1

「按照升序排列數組，然後我們會得到Binary Heap」。這是對的。 現在，它取決於您使用哪種算法按升序對數組進行排序。最佳分類算法的執行復雜度爲O(NLogN)。

雖然剛剛創建二進制堆的算法Build_Heap的複雜度爲O(N)。

除非和直到您使用非基於比較的排序方法（如Counting Sort），否則創建二進制堆的複雜性將至少爲O(NLogN)和O(N^2)。

因此，創建二進制堆的傳統方法是有利的。

雖然Counting Sort需要O(N)時間，但它需要額外的空間O(N)，而傳統Build_Heap將創建就地二元堆。