Loading AI tools
計算機科學中一種樹狀資料結構 来自维基百科,自由的百科全书
堆(Heap)是計算機科學中的一種特別的完全二叉樹。若是滿足以下特性,即可稱為堆積:「給定堆積中任意節點P和C,若P是C的母節點,那麼P的值會小於等於(或大於等於)C的值」。若母節點的值恆小於等於子節點的值,此堆積稱為最小堆積(min heap);反之,若母節點的值恆大於等於子節點的值,此堆積稱為最大堆積(max heap)。在堆積中最頂端的那一個節點,稱作根節點(root node),根節點本身沒有父節點(parent node)。
此條目需要補充更多來源。 (2024年8月11日) |
「堆積」的各地常用名稱 | |
---|---|
中國大陸 | 堆 |
臺灣 | 堆積 |
堆積始於J. W. J. Williams在1964年發表的堆積排序(heap sort),當時他提出了二元堆積樹作為此演算法的資料結構。
堆的實現通過構造二叉堆(binary heap),實為二叉樹的一種;由於其應用的普遍性,當不加限定時,均指該數據結構的這種實現。這種數據結構具有以下性質。
將根節點最大的堆叫做最大堆或大根堆,根節點最小的堆叫做最小堆或小根堆。
某些堆實現還支持其他的一些操作,如斐波那契堆支持檢查一個堆中是否存在某個元素。
為將元素X插入堆中,找到空閒位置,建立一個空穴,若滿足堆序性(英文:heap order),則插入完成;否則將父節點元素裝入空穴,刪除該父節點元素,完成空穴上移。直至滿足堆序性。這種策略叫做上濾(percolate up)。[1]
以上是插入到一個二叉堆的過程。
DeleteMin
,刪除最小元,即二叉樹的根或父節點。刪除該節點元素後,隊列最後一個元素必須移動到堆得某個位置,使得堆仍然滿足堆序性質。這種向下替換元素的過程叫作下濾。
堆(通常是二叉堆)常用於排序。這種算法稱作堆排序。
主要運用堆的排序以選擇優先。
在隊列中,調度程序反覆提取隊列中第一個作業並運行,因為實際情況中某些時間較短的任務將等待很長時間才能結束,或者某些不短小,但具有重要性的作業,同樣應當具有優先權。堆即為解決此類問題設計的最佳數據結構。[1]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.