make heap……創建堆比priority_queue快？快多少？快在哪裡

01-08

zhx神犇說了一下，但只是提了一下

謝邀。

std::priority_queue 只不過是把 heap 那一套 function 封裝成 adapter 了，演算法都是一樣的，你說能快多少？

有追求這兩個哪個快的時間還不如查查 pb_ds 的資料，學學用用那些不同演算法的堆。

針對提問：make_heap 的複雜度是 O(n)，低於一個一個插進堆中的 O(nlogn)。就算複雜度同階，普通數組仍比 vector 具有小的多的常數。

庫中的 priority_queue 是通過在 vector 上調用 push_heap、pop_heap 等函數實現的，而你手動實現是在數組上調用上述函數實現。

顯然你的手動數組實現絕對不會慢於 vector 實現。（想想，每次 O(logn) 次的大常數 vector 操作……）

實測在 cena 上速度差異最嚴重，因為 vector 效率極低，接近 O(logn)，因此使用 priority_queue 的效率接近 O(log^2n)，而手動實現的效率還是非常高，在 O2 下甚至快於完全手寫的二叉堆。

另外，並不資磁在比賽（特別是 NOIP）中使用 pb_ds，因為其能否使用還有待爭論。據某不願意透露姓名的著名大爆搜遊戲題出題人說，出題人有手動 ban 掉非法代碼的權力。