構建最小/最大二元堆

Question

鑑於中序遍歷列表，什麼是創建一個二進制最小值/最大值堆的最佳方式？

我想用下面的結構來限制：

1. 沒有數組中的二進制堆使用。實現是基於節點的。 BinaryNode { value, parent, l_child, r_child }

2. 讓我們來堅持Max-Heap。

問：我們可以做的比這涉及BubbleDown標準插好。

Answer 1

沒有爲從值的集合，是漸近比只是做Ñ氣泡步驟更快構建最大堆優雅線性時間算法。這個想法是建立較小的MAX-堆森林，然後連續直到所有元素都被加入到一個單一的最大堆它們合併在一起配對。使用精確的分析，可以證明，該算法在O（n）的時間運行具有非常好的常數因子。許多標準庫包含此功能;例如，C++有std::make_heap算法。

有關此算法的詳細信息，包括算法的草圖，正確性證明和運行時分析，看看這個早些時候問題：https://stackoverflow.com/a/6300047/501557

希望這有助於！