本文會(huì)針對(duì)樹這種數(shù)據(jù)結(jié)構(gòu)，進(jìn)行相關(guān)內(nèi)容的闡述。其實(shí)本文應(yīng)該算是一篇讀書筆記。

文章首發(fā)于我的個(gè)人博客網(wǎng)站：https://blog.fstars.wang/posts/alg-tree-analy-in-js/

內(nèi)容總覽

• 樹
• 二叉樹
• 二叉查找樹
• 堆和堆的一些操作
• 堆排序
• 堆的應(yīng)用

另外，我先在這里給出 js 實(shí)現(xiàn)的源碼地址：

1. 樹和二叉樹
2. 堆的實(shí)現(xiàn)
3. 堆排序

樹

這里簡單說下樹是什么。

樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)。樹中的元素稱為“節(jié)點(diǎn)”。每個(gè)節(jié)點(diǎn)有有限個(gè)子節(jié)點(diǎn)或沒有子節(jié)點(diǎn)，且樹中不能有環(huán)路。

樹

兩個(gè)相連的節(jié)點(diǎn)的關(guān)系稱為 “父子關(guān)系”。

一些術(shù)語（摘自維基百科）：

1. 節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)含有的子樹的個(gè)數(shù)稱為該節(jié)點(diǎn)的度；
2. 樹的度：一棵樹中，最大的節(jié)點(diǎn)的度稱為樹的度；
3. 葉節(jié)點(diǎn)或終端節(jié)點(diǎn)：度為零的節(jié)點(diǎn)；
4. 非終端節(jié)點(diǎn)或分支節(jié)點(diǎn)：度不為零的節(jié)點(diǎn)；
5. 父親節(jié)點(diǎn)或父節(jié)點(diǎn)：若一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)；
6. 孩子節(jié)點(diǎn)或子節(jié)點(diǎn)：一個(gè)節(jié)點(diǎn)含有的子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)；
7. 兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn)；
8. 節(jié)點(diǎn)的層次：從根開始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層，以此類推；
9. 深度：對(duì)于任意節(jié)點(diǎn)n，n的深度為從根到n的唯一路徑長，根的深度為0；
10. 高度：對(duì)于任意節(jié)點(diǎn)n，n的高度為從n到一片樹葉的最長路徑長，所有樹葉的高度為0；
11. 堂兄弟節(jié)點(diǎn)：父節(jié)點(diǎn)在同一層的節(jié)點(diǎn)互為堂兄弟；
12. 節(jié)點(diǎn)的祖先：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)；
13. 子孫：以某節(jié)點(diǎn)為根的子樹中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫。
14. 森林：由m（m>=0）棵互不相交的樹的集合稱為森林；

二叉樹

樹有很多種類，比如二叉樹、三叉樹、四叉樹等。但最常用的樹就是二叉樹。

二叉樹是每個(gè)節(jié)點(diǎn)最多只有兩個(gè)分支的樹結(jié)構(gòu)，這兩個(gè)分支的節(jié)點(diǎn)被稱為 左子節(jié)點(diǎn) 和 右子節(jié)點(diǎn)。

滿二叉樹，指的是除了葉子節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)的二叉樹。

完全二叉樹：除了最后一層，其他層的節(jié)點(diǎn)個(gè)數(shù)都要最大，且最后一層的節(jié)點(diǎn)都靠左排列的二叉樹。

滿二叉樹

可能有人覺得完全二叉樹看起來好像沒什么用，怎么還靠左邊的，靠中間不行嗎？其實(shí)靠左是因?yàn)槎鏄涞钠渲幸环N數(shù)據(jù)存儲(chǔ)方式是用數(shù)組存儲(chǔ)，使用完全二叉樹就不會(huì)浪費(fèi)數(shù)組的空間（不會(huì)出現(xiàn)一些數(shù)組元素不存儲(chǔ)的情況）

二叉樹的存儲(chǔ)

1. 鏈?zhǔn)酱鎯?chǔ)法

鏈?zhǔn)酱鎯?chǔ)法，是通過指針的方式來記錄父子關(guān)系的一種方法。它有點(diǎn)類似鏈表，每個(gè)節(jié)點(diǎn)除了保存自身的數(shù)據(jù)外，還會(huì)有l(wèi)eft 和 right 兩個(gè)指針，指向另外兩個(gè)節(jié)點(diǎn)。

const node = {
    data: 1,         // 節(jié)點(diǎn)保存的數(shù)據(jù)
    left: node2,    // 左子節(jié)點(diǎn)指向 node2 節(jié)點(diǎn)
    right: null     // null 表示沒有右子節(jié)點(diǎn)
}

2. 順序存儲(chǔ)法

用數(shù)組存儲(chǔ)。為了代碼可讀性更好，我們一般會(huì)選擇浪費(fèi)數(shù)組下標(biāo)為 0 的存儲(chǔ)位置，即根節(jié)點(diǎn)在下標(biāo)為 1 的位置。 這時(shí)父節(jié)點(diǎn)和左右節(jié)點(diǎn)的下標(biāo)關(guān)系如下：

left = 2 * i;
right = 2 * i + 1;
i = left / 2;   
i = right / 2;  // 這里是向下取整

這里的 i 為父節(jié)點(diǎn)下標(biāo)，left 和 right 為兩個(gè)子節(jié)點(diǎn)下標(biāo)。

這里有個(gè)要注意的地方：這里的父節(jié)點(diǎn)的下標(biāo)值是子節(jié)點(diǎn)除以 2 并 取整。（有些編程語言的整數(shù)相除，會(huì)自動(dòng)將得到的結(jié)果去掉小數(shù)部分，而一些編程語言，比如 Javascript，是會(huì)得到小數(shù)的，需要手動(dòng)向下取整。）

如果你就是不想浪費(fèi)數(shù)組的第一個(gè)元素的存儲(chǔ)位置，誓要將根節(jié)點(diǎn)保存在數(shù)組的第一個(gè)位置。那此時(shí)父節(jié)點(diǎn)和子節(jié)點(diǎn)的下標(biāo)關(guān)系為：

left = 2 * i + 1;
right = 2 * i + 2;
i = (left - 1) / 2;
i = (right - 1) / 2;

如果某棵二叉樹是一棵完全二叉樹，那用數(shù)組存儲(chǔ)無疑是最節(jié)省內(nèi)存的一種方式。

二叉樹的遍歷

這個(gè)是很常見的面試題呢。

1. 前序遍歷

根左右。 這里的“前”描述的是根節(jié)點(diǎn)，即根節(jié)點(diǎn)最先輸出（打?。?，然后輸出左子樹，最后輸出右子樹。

代碼中的樹是用 鏈?zhǔn)酱鎯?chǔ)法 存儲(chǔ)的。代碼實(shí)現(xiàn)用到了 遞歸。

// 前序遍歷（根左右）
preOrder() {
    let order = '';
    r(this.root);

    order = order.slice(0, order.length - 1); // 這里只是去掉最后的一個(gè)逗號(hào)。
    return order;

    // 遞歸函數(shù)
    function r(node) {
        if (!node) return;
        order += `${node.val},`;
        r(node.left);
        r(node.right);
    }
},

2. 中序遍歷

左根右。 “中序”的這個(gè)“中”也是指的根節(jié)點(diǎn)的輸出位置是中間。中序遍歷先輸出左子樹，再輸出根節(jié)點(diǎn)，最后輸出右子樹。

// 中序遍歷
inOrder() {
    let order = '';
    r(this.root);

    order = order.slice(0, order.length - 1);
    return order;

    // 遞歸函數(shù)
    function r(node) {
        if (!node) return;
        r(node.left);
        order += `${node.val},`;
        r(node.right);
    }
},

3. 后續(xù)遍歷

左右根。 先打印左子樹，然后打印根節(jié)點(diǎn)，最后打印右子樹。

postOrder() {
    let order = '';
    r(this.root);

    order = order.slice(0, order.length - 1);
    return order;

    // 遞歸函數(shù)
    function r(node) {
        if (!node) return;
        r(node.left);
        r(node.right);
        order += `${node.val},`;
    }
},

4. 層次遍歷

層次遍歷，就是每層的節(jié)點(diǎn)從左往右遍歷，直到遍歷完所有節(jié)點(diǎn)。如果是順序存儲(chǔ)法存儲(chǔ)的，數(shù)組從前往后遍歷即可。如果是鏈?zhǔn)酱鎯?chǔ)法存儲(chǔ)樹，實(shí)現(xiàn)就會(huì)復(fù)雜一些，要用到一個(gè)隊(duì)列

levelOrder() {
    if (this.root == null) return '';
    let a = [],
        left, right;
    a.push(this.root);

    // 節(jié)點(diǎn)入隊(duì)，指針指向頭部元素，如果它有l(wèi)eft/right，入隊(duì)。
    // 指針后移，繼續(xù)同樣步驟。。。直至指針跑到隊(duì)列尾部后面去。。。
    for(let i = 0; i < a.length; i++) {     // 需要注意的是，數(shù)組 a 的長度是動(dòng)態(tài)變化的（不停變長）
        left = a[i].left;
        if (left) a.push(left);

        right = a[i].right;
        if (right) a.push(right);
    }
    return a.map(item => item.val).join(',');
}

二叉查找樹

二叉查找樹，也叫做 二叉搜索樹。此外它也被稱為 二叉排序樹，因?yàn)橹行虮闅v就可以得到有序的數(shù)據(jù)序列（非常高效，時(shí)間復(fù)雜度是 O(n)）。

二叉查找樹的作用是快速查找。除了快速查找，它也支持快速插入、刪除數(shù)據(jù)。

那么什么樣的二叉樹才是二叉查找樹呢？二叉查找樹是任意一個(gè)節(jié)點(diǎn)的左子樹的節(jié)點(diǎn)都小于該節(jié)點(diǎn)，任意一個(gè)節(jié)點(diǎn)的的右子樹的節(jié)點(diǎn)都大于該節(jié)點(diǎn)的二叉樹。

根據(jù)定義，二叉查找樹是 不允許有兩個(gè)數(shù)據(jù)相同的節(jié)點(diǎn)的。

二叉查找樹的查找操作

先和根節(jié)點(diǎn)的值比較，如果相等，就找到了；如果要查找的值比根節(jié)點(diǎn)小，就在左子樹中遞歸查找；如果比根節(jié)點(diǎn)大，就在右子樹中遞歸查找。

find(val) {
    // 假設(shè)二叉樹沒有重復(fù)數(shù)據(jù)
    let p = this.root;
    while(p != null) {
        if (val == p.val) return p;
        else if (val < p.val) p = p.left;
        else p = p.right;
    }
    return null; // 沒找到
},

二叉查找樹的插入操作

類似查找操作。從根節(jié)點(diǎn)開始，比較要插入的數(shù)據(jù)和節(jié)點(diǎn)的大小關(guān)系。如果要插入的數(shù)據(jù)比當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)大，且右子樹為空，就作為該節(jié)點(diǎn)的右子節(jié)點(diǎn)；如果右子樹不為空，就繼續(xù)遞歸右子樹。同理，比當(dāng)前節(jié)點(diǎn)數(shù)據(jù)小，就看該節(jié)點(diǎn)的左子樹，若為空，插入到左子節(jié)點(diǎn)位置；若不為空，就遞歸左子樹。

// 插入節(jié)點(diǎn)
insert(val) {
    if (this.root == null) {
        this.root = node;
        return true;
    }

    let node = new Node(val);
    let p = this.root;

    while (p != null) {
        if (val < p.val) {
            if (p.left == null) {
                p.left = node;
                return this.inOrder(); 
                // 返回個(gè)中序遍歷的結(jié)果，檢查插入是否正確。（你可以改為 true，表示插入成功）
            }
            p = p.left;
        }
        else if (val > p.val) {
            // preP = p;
            if (p.right == null) {
                p.right = node;
                return this.inOrder();
            }
            p = p.right;
        }

        if (val == p.val) {
            console.warn('二叉樹中含相同值的數(shù)據(jù)，無法插入')
            return false;
        }
    }
},

二叉查找樹的刪除操作

這個(gè)就很復(fù)雜，要分三種情況：

1. 要?jiǎng)h除的節(jié)點(diǎn)沒有子節(jié)點(diǎn)：直接更新父節(jié)點(diǎn)指向其的指針為 null
2. 要?jiǎng)h除的節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)：父節(jié)點(diǎn)中指向要?jiǎng)h除的節(jié)點(diǎn)的指針，更新為要?jiǎng)h除節(jié)點(diǎn)的那個(gè)子節(jié)點(diǎn)。
3. 要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)：找到右子樹中的最小節(jié)點(diǎn)（一般是葉子節(jié)點(diǎn)），替換到要?jiǎng)h除的節(jié)點(diǎn)上。（當(dāng)然你也可以選擇找左子樹的最大節(jié)點(diǎn)）

// 刪除
remove(val) {
    // 假設(shè)二叉樹沒有重復(fù)數(shù)據(jù)
    let p = this.root;
    let parent, dir;   // 暫不考慮只有根節(jié)點(diǎn)一個(gè)的情況。
    while(p != null) {
        
        if (val == p.val) {
            // 要?jiǎng)h除的節(jié)點(diǎn)沒有子節(jié)點(diǎn)
            if (p.left == null && p.right == null) {
                parent[dir] = null;
                return true;
            } 
            // 要?jiǎng)h除的節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)
            else if (p.left == null && p.right != null) {
                parent[dir] = p.right
                console.log('只有右節(jié)點(diǎn)');
                return true;
            } else if (p.right == null && p.left != null) {
                parent[dir] = p.left;
                console.log('只有左節(jié)點(diǎn)');
                return true;
            } 
            
            // 要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)
            // 可以將右子樹的最小結(jié)點(diǎn)替換到被刪除的節(jié)點(diǎn)位置，并刪除這個(gè)最小節(jié)點(diǎn)
            // 當(dāng)然你也可以在左子樹中找最大節(jié)點(diǎn)。
            else if (p.left != null && p.right != null) {
                // 因?yàn)橐涗涀钚」?jié)點(diǎn)的父節(jié)點(diǎn)，所以不能用 this.findMin()
                // 第一步：找出最小節(jié)點(diǎn) minP
                let minParent,
                    minP = p;
                while (minP) {
                    if (minP.left == null) {
                        // 找到。
                        break;
                        // return minP;
                    }
                    minParent = minP;
                    minP = minP.left;
                }

                // 第二步：替換（把數(shù)據(jù)轉(zhuǎn)移過去即可）
                p.val = minP.val;

                // 第三步：刪除最小節(jié)點(diǎn)
                if (minP.right == null) {
                    minParent.left = null;
                    console.log('最小節(jié)點(diǎn)沒有子節(jié)點(diǎn)');
                    return true;
                } else if (minP.right != null) {
                    minParent.left = minP.right;
                    console.log('最小節(jié)點(diǎn)只有右節(jié)點(diǎn)');
                    return true;
                } 

            }
            return p;
        } 

        // 繼續(xù)找要?jiǎng)h除的節(jié)點(diǎn)。
        else {
            parent = p;
            if (val < p.val) {
                p = p.left;
                dir = 'left';
            } else {
                p = p.right;
                dir = 'right';
            }
        }
    }
    return null;   // 沒找到

    // 要保存父節(jié)點(diǎn)，且要記錄當(dāng)前節(jié)點(diǎn)是父節(jié)點(diǎn)的 left 還是 right。
},

還有另一種簡單的刪除操作，就是標(biāo)記一個(gè)節(jié)點(diǎn)為“已刪除”，雖然操作變得簡單了，但“已刪除”的數(shù)據(jù)仍然在內(nèi)存中，會(huì)浪費(fèi)內(nèi)存空間。

支持重復(fù)數(shù)據(jù)的二叉查找樹

一般來說，根據(jù)定義，二叉查找樹是不允許有重復(fù)數(shù)據(jù)的。但實(shí)際開發(fā)中，數(shù)據(jù)一般不可能不重復(fù)。所以我們看看怎么使二叉查找樹支持重復(fù)數(shù)據(jù)存儲(chǔ)：

1. 節(jié)點(diǎn)改為可以存儲(chǔ)多個(gè)數(shù)據(jù)，而不是只有一個(gè)數(shù)據(jù)。可以考慮鏈表和動(dòng)態(tài)擴(kuò)容數(shù)組。
2. 插入過程中，如果發(fā)現(xiàn)已經(jīng)有重復(fù)的數(shù)據(jù)了，就放到這個(gè)節(jié)點(diǎn)的右子樹的最左節(jié)點(diǎn)的位置（當(dāng)然你也可以考慮放到左子樹的最右邊節(jié)點(diǎn)位置）。如果是這樣的實(shí)現(xiàn)的話，查找操作和刪除操作就要跟著做一些小修改。

平衡二叉樹

維基百科的定義：平衡二叉搜索樹（英語：Balanced Binary Tree）是一種結(jié)構(gòu)平衡的二叉搜索樹，即葉節(jié)點(diǎn)高度差的絕對(duì)值不超過1，并且左右兩個(gè)子樹都是一棵平衡二叉樹。它能在O(logn)內(nèi)完成插入、查找和刪除操作，最早被發(fā)明的平衡二叉搜索樹為AVL樹。

平衡二叉樹的發(fā)明，是為了解決二叉樹在不斷插入、刪除等動(dòng)態(tài)操作后，導(dǎo)致時(shí)間復(fù)雜度退化的問題。它會(huì)讓二叉樹盡量地保持平衡，即保持 矮矮胖胖* 的樣子。

平衡二叉樹中，最為有名的就是 紅黑樹 了。是不是經(jīng)常有群友開玩笑說他們招人，要求當(dāng)場手寫紅黑樹呢。紅黑樹的性能很好，廣泛用于實(shí)際開發(fā)中，其他的平衡二叉樹則很少出現(xiàn)在人們的視野之中。

平衡二叉樹的實(shí)現(xiàn)很復(fù)雜，就暫時(shí)不詳細(xì)分析了。

堆

堆是一個(gè) 每個(gè)節(jié)點(diǎn)的數(shù)據(jù)都大于等于（或小于等于）它的子節(jié)點(diǎn)的完全二叉樹。

對(duì)于每個(gè)節(jié)點(diǎn)的值都大于等于子樹中每個(gè)節(jié)點(diǎn)值的堆，我們叫作 大頂堆。對(duì)于每個(gè)節(jié)點(diǎn)的值都小于等于子樹中每個(gè)節(jié)點(diǎn)值的堆，我們叫作 小頂堆。

因?yàn)槎咽峭耆鏄?，所以我們用?shù)組存儲(chǔ)。

1. 插入一個(gè)元素

插入元素到堆，具體做法是插入到數(shù)組的末尾，然后通過 堆化 操作，對(duì)樹進(jìn)行調(diào)整，重新變成堆。

堆化（heapify），是指一個(gè)節(jié)點(diǎn)，不停地向上或向下進(jìn)行交換，直到找到合適的位置，使當(dāng)前的二叉樹變成堆。

插入時(shí)進(jìn)行的堆化是 從下往上堆化。新插入的元素位于末尾，需要不停地和父元素進(jìn)行比較和進(jìn)行交換，直到找到合適的位置結(jié)束，此時(shí)樹就會(huì)又變成堆。

// 入堆，從下往上堆化。
insert(val) {
    // count 指的是當(dāng)前數(shù)組存儲(chǔ)數(shù)據(jù)的大小，n 為 數(shù)組的容量
    //（當(dāng)然js的數(shù)組是動(dòng)態(tài)數(shù)組。這里的 n 是我手動(dòng)加的限制）
    if (this.count >= this.n) {   
        console.log('堆滿了，別加了??！')
        return;
    }
    this.count++;

    let a = this.a;  // a 是存儲(chǔ)數(shù)據(jù)的數(shù)組
    a[this.count] = val;

    let i = this.count,
        j = Math.floor(i/2);   // 臨時(shí)存儲(chǔ) i/2

    while (i > 1 && a[i] > a[j]) {
        [a[i], a[j]] = [a[j], a[i]];
        i = j;
        j = Math.floor(i/2);
    }
    return true;
}

2. 刪除堆頂元素

刪除了堆頂元素后，我們需要把最后一個(gè)元素移動(dòng)到堆頂元素位置，然后進(jìn)行 從上往下的堆化。

從上往下堆化具體的實(shí)現(xiàn)是：最后一個(gè)元素替換掉堆頂元素后，就比較堆頂元素和它的兩個(gè)子節(jié)點(diǎn)，看看誰最大，如果不是堆頂元素最大，堆頂元素就和值最大的子節(jié)點(diǎn)交換。重復(fù)上面的步驟，直到當(dāng)前節(jié)點(diǎn)最大或者當(dāng)前節(jié)點(diǎn)成為葉子節(jié)點(diǎn)（到底了）。

// 刪除堆頂元素
removeMax() {
    if (this.count == 0) return false;  // 堆為空

    this.a[1] = this.a[this.count];
    this.a[this.count] = undefined;
    this.count--;

    // 從上往下 堆化
    let i = 1,
        maxPos = i;

    while (true) {
        if (i * 2 <= this.count && this.a[i*2] > this.a[maxPos]) maxPos = i * 2;
        if (i * 2 + 1 <= this.count && this.a[i*2 + 1] > this.a[maxPos]) maxPos = i * 2 + 1;
        if (maxPos == i) {
            break;
        }
        [this.a[i], this.a[maxPos]] = [this.a[maxPos], this.a[i]];
        i = maxPos;
    }
    return true;
}

堆排序

堆排序算法分兩個(gè)步驟：先建堆，然后進(jìn)行排序。

1. 建堆

對(duì)數(shù)組進(jìn)行 原地 建堆。原地是指在原數(shù)組上進(jìn)行操作，不需要另開一個(gè)堆。

建堆的方式有兩種：

1. 借助前面提到的插入操作的方式。

這里就是往 “堆區(qū)域” 末尾插入元素，然后從下往上堆化。類似插入排序，我們將數(shù)組分為 “堆區(qū)域” 和 “未處理區(qū)域”，不停地將“未處理區(qū)域”里的元素插入到“堆區(qū)域” 中，直到遍歷完整個(gè)數(shù)組。

2. 從最后一個(gè)非葉子節(jié)點(diǎn)開始往前，進(jìn)行 從上往下的堆化。

葉子節(jié)點(diǎn)因?yàn)闆]有子節(jié)點(diǎn)，所以不需要進(jìn)行堆化。另外，對(duì)于完全二叉樹來說，最后一個(gè)非葉子節(jié)點(diǎn)的下標(biāo)為 i / 2（i 從1開始，你可以自己畫個(gè)完全二叉樹驗(yàn)證一下）。

建堆的復(fù)雜度是 O(n)。

2. 排序

將堆頂節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)進(jìn)行交換，然后對(duì)剩余的 n -1 個(gè)元素進(jìn)行從上往下堆化。然后我們?cè)俳粨Q堆頂節(jié)點(diǎn)和第 n - 1 個(gè)元素，然后對(duì)剩余的 n - 2 個(gè)元素進(jìn)行從上往下堆化，就這樣不停地交換和堆化，直到堆中只有一個(gè)元素。

性能分析

1. 堆排序的時(shí)間復(fù)雜度是 O(nlogn)。

建堆的時(shí)間復(fù)雜度是 O(n)，排序過程的時(shí)間復(fù)雜度是 O(nlogn)，所以堆排序的時(shí)間復(fù)雜度是 O(nlogn)。

2. 堆排序是不穩(wěn)定的排序

因?yàn)榕判蜻^程中，堆頂元素會(huì)和堆的最后一個(gè)元素進(jìn)行交換，導(dǎo)致排序不穩(wěn)定。

3. 堆排序是原地排序

堆排序和快速排序的比較

快速排序比堆排序好。理由如下：

1. 堆排序訪問數(shù)據(jù)方式不好，是跳著訪問數(shù)組元素的，不利于 CPU緩存。
2. 堆排序的交換操作更多。堆排序的建堆完成后，會(huì)降低數(shù)據(jù)的有序堆，這樣會(huì)使得交換操作變多。

代碼實(shí)現(xiàn)是在原數(shù)組上進(jìn)行數(shù)據(jù)交換的。

堆的應(yīng)用

1. 優(yōu)先級(jí)隊(duì)列

優(yōu)先級(jí)可以用于解決 合并有序小文件、高性能定時(shí)器 等問題。

2. 求 TopK 數(shù)據(jù)

這個(gè)就是維護(hù)一個(gè)大小為 k 的小頂堆。將未入堆的元素和堆頂元素比較，如果比堆頂元素大，就入堆，直到所有元素都入堆后，這個(gè)堆就是 TopK 元素了。

時(shí)間復(fù)雜度是 O(nlogK)。最壞情況下，一次堆化需要 O(logK)，要進(jìn)行 n 次堆化操作。

3. 求中位數(shù)

如果是靜態(tài)數(shù)據(jù)，先排序，然后求中位數(shù)即可，這樣邊際成本低。

如果是動(dòng)態(tài)數(shù)據(jù)，那就需要維護(hù)一個(gè) 大頂堆 和一個(gè)小頂堆。要求大頂堆的數(shù)量等于小頂堆的數(shù)量或小頂堆的數(shù)量+1，且大頂堆的元素都小于小頂堆的元素。中位數(shù)即大頂堆的堆頂元素。

大頂堆和小頂堆

初始化的時(shí)候，可以用類似 topK 算法，弄一個(gè)數(shù)量為 k 為 n/2 的小頂堆放數(shù)組右邊，然后將剩余的元素轉(zhuǎn)換為大頂堆。

然后每次添加數(shù)據(jù)的時(shí)候，都會(huì)分別比較大頂堆的堆頂元素和小頂堆的堆頂元素，決定插入到哪邊。插入后，還要進(jìn)行一些堆的插入和刪除操作，以維持這兩個(gè)堆數(shù)量要差不多相同（左右元素?cái)?shù)量相同或者左邊堆比右邊多一個(gè)）。

除了可以利用堆求中位數(shù)，我們還可以利用堆計(jì)算 “99% 響應(yīng)時(shí)間” 的問題。即維護(hù)數(shù)量為 99/n 的大頂堆和數(shù)量為 1/n 的小頂堆。

參考文獻(xiàn)

1. 維基百科——樹 (數(shù)據(jù)結(jié)構(gòu))
2. 數(shù)據(jù)結(jié)構(gòu)與算法之美