More Heap

今天在看意春木的 軟韌體工程師面試- C語言與OS作業系統 常見題目(筆試考題),讀到有關描述 heap 概念的一段話:

heap:
台灣正體中文稱為堆積,大陸叫做堆。
不可預測的因素造成上述的stack區塊不適合運用。
所以當資訊為動態配置產生,系統會存放在另外一塊空間,稱之為『Heap』
(注意這裡的Heap跟資料結構中的Heap不相關,可別會錯意!)。

其中令我疑惑的是最後這句括號中的補充,因此做了些研究,先是複習了一下資料結構中的 heap,最常見也基本的三個重點:

  1. 是一種樹狀結構
    => 不懂為什麼,因為堆疊錐形金字塔像是一顆樹狀結構?
  2. 最常以 array 實作
    => 我覺得這個原因是,當不同 level 的元素(child and parent)要做比較和交換時,會比 linked list 要方便及快速
  3. 最常被拿來實作 priority queue
    => 因為當一個物件要進入這個 priority queue 時,一定是從 queue 的最尾端 (堆積樹的最右下一個位置) 插入,然後才進行優先權檢查看應該調整到哪個位置 (不可能一來就排在最先或最後,那就沒有 priority 了),而 head 的調整原理很符合這個規則需求

然後我搜尋了一下關鍵字heap in memory data structure,找到的第一個結果是 stackoverflow 的提問,就是在討論『C 執行時期記憶體配置中的 heap 與資料結構中討論的 heap 有什麼不同』,原文連結:http://stackoverflow.com/questions/1699057/why-are-two-different-concepts-both-called-heap

票選最高的一個解答為:

Donald Knuth says (The Art of Computer Programming, Third Ed., Vol. 1, p. 435):

==Several authors began about 1975 to call the pool of available memory a “heap."==

He doesn’t say which authors and doesn’t give references to any specific papers, but does say that the use of the term “heap" in relation to priority queues is the traditional sense of the word.

下面的留言和解答也有一些支持用 pool 來稱呼 memory pool 的概念

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Google photo

您的留言將使用 Google 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 /  變更 )

連結到 %s