關於C++中的make_heap算法

http://www.cplusplus.com/reference/algorithm/make_heap/關於C++中的make_heap算法

在此鏈接中。它說：

內部，堆是一棵樹比其自身的價值，其中每個節點鏈接值不大於。在堆由make_heap產生，在樹中，而不是的元素由存儲器消耗鏈接被確定是由所述序列中的絕對位置來確定的特定位置，帶*第一是始終在最高值堆。

關於「由其在序列中的絕對位置決定」。我困惑在這裏。它也說「堆是一棵樹，其中每個節點鏈接到不大於其自己的值的值」

這兩個句子是否矛盾？這裏很困惑。 C++中的堆究竟是什麼樹？

希望的任何善良的人能幫助我非常感謝

來源

2011-04-09 user699656

該算法的一個很好的解釋是在這個問題：http://stackoverflow.com/questions/5057562。 – 2011-04-09 06:43:09

您可以將二進制堆數據結構（不是內存堆）排列在數組中，而將其視爲完整的二叉樹。您應該閱讀並理解堆排序的實現。查看Cormen等人在「算法導論」中有關Heapsort的章節 – 2011-04-09 07:11:55

我建議閱讀http://en.cppreference.com/w/cpp/algorithm/make_heap，而不是[** cplusplus.com上的任何內容**]（http://stackroulette.com/programmers/88241/whats-wrong-with-cplusplus-com）。內部是特定於實現的。 – Johnsyweb 2012-12-29 07:29:20

這就是說，堆有一個典型的樹狀結構，其中每個「父」節點大於或等於「子」節點的值（「...每個節點鏈接到的值不是大於自己的價值......「）。它接着說，而不是使用鏈接（即指針，例如，一個結構（就像你會用於鏈表）），它使用就地存儲器（也稱爲數組 - 「」 ...由序列中的絕對位置決定......「）。

*首先是堆上的第一個元素（或最大/最小值，取決於比較器函數），並且始終位於數組的第[0]個索引處。對於每個索引i，孩子都位於[2 * i + 1]和[2 * i + 2]。

希望這會有所幫助。

來源

2011-04-09 07:05:54

如果你看堆實現你看到樹作爲數組實現的。您可以在索引2 * i+1和2 * i +2索引i處的節點下找到這些值。所以它是一棵樹，你可以通過它們在數組中的絕對位置訪問這些元素。

來源

2011-04-09 06:41:50 flolo

換句話說，算法*計算鏈接，所以結構不需要*存儲*它。 – Potatoswatter 2011-04-09 06:52:47

@Patatoswatter：對。 – flolo 2011-04-09 06:54:45

關於C++中的make_heap算法

回答

相關問題