構建堆原則 - 在C++中實現

Question

我的作業有些麻煩。我被要求實施一個優先隊列，在C++中使用堆。

當搜索代碼示例，創建一個堆，我多次遇到在此定義：

數組一個表示堆甲是具有兩個屬性的數組：

- 長度，陣列中元素的數量

- 堆大小，存儲在a中的堆元素的數量rray

所以我的問題是這樣的：什麼是A？我是否需要自己實現它（比方說，創建一個包含3個字段的類堆 - 元素，長度和heap_size數組）？

我只是不知道如何開始。

Answer 1

二進制堆數據結構通常繪製爲具有某些屬性的二叉樹，但通常使用普通數組實現。原因是數組版本使用的內存少於明確的二叉樹，並且操作起來更容易。因此，您所看到的陣列A是保存堆中所有值的陣列。

你看到表示陣列（長度），它跟蹤多大的存儲空間是如何可用的原始總大小，並且您正在實際使用該陣列內的元件的數目的兩個字段（按堆大小爲）。當你向堆中插入一個元素時，你需要確保它存在的空間，可能重新分配數組變大並複製現有的元素，然後需要運行冒泡操作來插入新元素進入堆。

儘管如此，通過在動態數組之上堆疊堆（例如C++ std::vector或Java ArrayList），您將回避維護數組和這兩個字段的邏輯。這樣，跟蹤存儲空間和增加數組的邏輯就會自動處理。

根據分配的參數，因爲這是在C++正在做，你可能要考慮從<algorithm>頭的std::make_heap，std::push_heap和std::pop_heap算法。他們可以很容易地在現有容器（如std::vector）上實現堆。事實上，這就是典型的std::priority_queue類。

如果您需要自己實施堆操作，則可能需要檢出the description of a binary heap given in this assignment handout，這似乎與您所得到的分配密切匹配。

希望這會有所幫助！