堆和樹有什麼區別？堆為什麼要叫堆，不叫樹呢？

01-06

heap為什麼要叫heap不叫tree呢？ heap這個名字是誰第一個提出的？

為什麼這麼叫不知道。

區別是堆的兒子不分左右。

當然，還有進階版的分左右的堆，

叫作左偏樹～

來一個離題的開頭

heap和tree結合，生了個孩子叫treap

中文名叫樹堆。

首先它每個節點有2個值value和weight

其中只看weight的話，滿足heap二叉堆的特性(父親比兒子都小/大)，只看value的話，滿足排序二叉樹特性(以左兒子為根的子樹元素都比父親小，右兒子為根的子樹都比父親大)

value是要維護的值，weight是隨機生成的值。由於隨機生成的堆使整棵treap變得平衡(嚴格證明請谷歌百度～)，所以treap是一種比較短小精悍的平衡樹的實現～

廢話結束，回歸題目(莫名押韻)

只要無環無向聯通圖都叫樹，具體就是n個點n-1條無向邊連接且任意兩點聯通的一種拓撲結構

如果我們選定一個節點作為根，那麼這棵樹就是有根樹，遍歷一遍就可以確定所有的父親-兒子的關係了。。。

如果一棵有根樹的每一個結點至多有兩個兒子，那麼這棵樹稱為二叉樹

如果一棵二叉樹的每一個節點都帶著一個值，且父親的值總是比兒子的值要大，我們稱這棵樹為大頂二叉堆，如果是父親比兒子都要小，那就是小頂二叉堆，統稱為二叉堆。(其實一般都把二叉兩個字省略掉，畢竟通常說的堆都是二叉堆，然而堆不止二叉堆)。這一個良好的性質註定了堆可以用來當作優先隊列使用。

優先隊列支持以下操作

1.放一個元素進去

2.總是能取出一個最大的元素出來(大，小的規矩可以通過一個比較函數來定義)

顯然堆就是可以這麼做。

當然啦，之前說過堆不止二叉堆，還有更複雜的二項堆，斐波那契堆，配對堆等等。。。具體可查閱論文or演算法導論

總結，堆是一種特殊的樹。(結尾點題！)

Algorithms 232: Heapsort

所以我瞎猜一下是會不會因為Tree這個名字剛用過？

順便，作者是J. W. J. WILLIAM

首先說明一下，堆並不一定是完全二叉樹，平時使用完全二叉樹的原因是易於存儲，並且便於索引。

怎麼易於存儲呢？我們使用一個數組就完全可以存儲完全二叉樹。

又怎麼便於索引呢？首先如果我們對一棵滿二叉樹逐層進行編號，會發現，假設每一個節點的編號為 $i$ ，那麼它的左子節點編號是 $2 imes i$ ，而右子節點是 $2 imes i+1$ 。而完全二叉樹則是，我們在滿二叉樹刪掉一些節點之後，使用同樣的逐層編號的方式，不會導致其他節點的編號發生變化。顯而易見，刪除的就是葉子結點中比較靠右的那一部分。所以它易於索引，並且不必為了保持編號的性質而去定義一些空的節點。同時還能保持它的層數一直是 $log(n)$ 的，索引起來的話，路徑不會太長。同時我們在刪除節點的時候，很容易保持它的性質，就是把最右邊的葉子結點拿過去補上被刪除的節點，之後對樹進行調整保證符合性質就好。

所以大部分時間我們是使用完全二叉樹來存儲堆的，但是堆並不等於完全二叉樹，例如二項堆，斐波那契堆，就不屬於二叉樹。

那麼回歸題主的問題本身，堆這種數據結構存在的原因是什麼。它作為一個工具，讓什麼樣的問題變得簡單了。

如果僅僅是需要得到一個有序的序列，使用排序就可以很快完成，並不需要去組織一個新的數據結構。但是如果我們的需求是對於一個隨時會有更新的序列，我要隨時知道這個序列的最小值或最大值是什麼。顯然如果是線性結構，每次插入之後，假設原數組是有序的，那使用二分把它放在正確的位置也未嘗不可，但是插入的時候從數組中留出空位就需要 $O(n)$ 的時間複雜度，刪除的時候亦然。

可是如果我們將序列看作是一個集合，我們需要的是這個集合的一個最小值，並且，在它被任意劃分成為若干個子集的時候，這些子集的最小值我們也是知道的，這些子集被不斷劃分，我們依然知道這些再次被劃分出來的子集的最小值。而且我們去想辦法去保持這樣的一個性質，那麼這個問題是不是變得非常好解決了呢？那麼問題就轉換成了一種集合之間的關係，並且是非常明顯的一種包含關係，那麼最適合於解決這種集合上的關係的數據結構是什麼呢？那麼就是樹，所以就形成了這樣的一種樹，他的每一個節點都比它的子節點們小或者大。

當我們插入一個新的節點的時候，實際上我們需要去調整的大部分時候只是這棵樹上的一條路徑，也就是決定它在哪一個集合裡面，樹上的路徑長度相對於這個集合，由於是對數級別的，所以非常可以接受，那麼這種數據結構也就應運而生，而這個數據結構為什麼叫做堆，那就不知道了。

結合本篇答案開頭處對完全二叉樹的一個解釋，則可以得出我們現在通常使用的堆是怎麼產生的了。

堆有個特點是最大的或者最小的在最上面，那如果叫做樹，怎麼突顯這個特性呢？跟最大的或根最小的樹？不覺得麻煩嗎？一般堆東西，小的在上面，所以叫堆吧，對應出大的在上面。

堆是一種特殊的樹，特殊表現在是完全二叉樹，且父子結點上的元素有大小關係限制。

堆是一類特殊的樹，堆的通用特點就是父節點會大於或小於所有子節點。

看我簡單總結的這張圖吧。

堆是一種特殊的樹,它每個結點都有一個值，堆的特點是根結點的值最小（或最大），且根結點的兩個子樹也是一個堆。就類似一堆東西一樣，按照由大到小（或由小到大）「堆」起來。

堆有大根堆和小根堆，大根堆的堆結點也就是根結點是最大的，相反小根堆是最小的，他和二叉樹的區別在於，堆的左右子樹節點的值，大於或者等於堆結點的值，而二叉排序樹的左孩子比右孩子小，他是有一定的關係的。

堆本身是一個滿足堆條件的序列，但可以看成一個「完全二叉樹」的順序存儲。可以看這個數據結構視頻教程：Learn to programming Blog

樹難道不是僅僅為堆的一種實現方式嗎？怎麼堆就成了樹的一種了？

堆不止二叉堆一種實現方法。

樹也不止二叉樹一種樹。