樹的概念

有很多數(shù)據(jù)的邏輯關(guān)系并不是線性關(guān)系，在實際場景中箭启，常常存在著一對多缓呛，甚至是多對多的情況。
例如以下兩種場景：
組織結(jié)構(gòu)：

image.png

書的目錄：

image.png

有且僅有一個特定的稱為根的節(jié)點秧廉。
當n>1時，其余節(jié)點可分為m（m>0）個互不相交的有限集拣帽，每一個集合本身又是一個樹疼电，并稱為根的子樹。
一個標準的樹結(jié)構(gòu)：

image.png

image.png

image.png

二叉樹

二叉樹（binary tree）是樹的一種特殊形式。二叉炉旷，顧名思義护赊，這種樹的每個節(jié)點最多有2個孩子節(jié)點惠遏。注意砾跃，這里是最多有2個骏啰，也可能只有1個，或者沒有孩子節(jié)點抽高。

image.png

二叉樹節(jié)點的兩個孩子節(jié)點判耕，一個被稱為左孩子（left child），一個被稱為右孩子（right child）翘骂。這兩個孩子節(jié)點的順序是固定的壁熄，左孩子小于右孩子。

滿二叉樹

一個二叉樹的所有非葉子節(jié)點都存在左右孩子碳竟，并且所有葉子節(jié)點都在同一層級上，那么這個樹就是滿二叉樹

image.png

完全二叉樹

對一個有n個節(jié)點的二叉樹，按層級順序編號聪铺，則所有節(jié)點的編號為從1到n尼荆。如果這個樹所有節(jié)點和同樣深度的滿二叉樹的編號為從1到n的節(jié)點位置相同，則這個二叉樹為完全二叉樹

image.png

滿二叉樹要求所有分支都是滿的诈泼；而完全二叉樹只需保證最后一個節(jié)點之前的節(jié)點都齊全即可

二叉樹的存儲

二叉樹屬于邏輯結(jié)構(gòu)懂拾，可以使用鏈表和數(shù)組進行存儲。
1）鏈式存儲

image.png

二叉樹的每一個節(jié)點包含3部分：存儲數(shù)據(jù)的data變量铐达，指向左孩子的left指針岖赋，指向右孩子的right指針。
2）數(shù)組存儲
使用數(shù)組存儲時瓮孙，會按照層級順序把二叉樹的節(jié)點放到數(shù)組中對應(yīng)的位置上唐断。如果某一個節(jié)點的左孩子或右孩子空缺，則數(shù)組的相應(yīng)位置也空出來杭抠。

image.png

二叉查找樹

二叉查找樹(binary search tree)，二叉查找樹在二叉樹的基礎(chǔ)上增加了以下幾個條件：
如果左子樹不為空沮峡，則左子樹上所有節(jié)點的值均小于根節(jié)點的值
如果右子樹不為空疚脐，則右子樹上所有節(jié)點的值均大于根節(jié)點的值
左、右子樹也都是二叉查找樹邢疙，如下圖：

image.png

二叉查找樹要求左子樹小于父節(jié)點棍弄，右子樹大于父節(jié)點望薄，正是這樣保證了二叉樹的有序性。因此二叉查找樹還有另一個名字——二叉排序樹（binary sort tree）呼畸。

查找

例如查找值為4的節(jié)點痕支，步驟如下：

1. 訪問根節(jié)點6，發(fā)現(xiàn)4<6蛮原。
2. 訪問節(jié)點6的左孩子節(jié)點3卧须，發(fā)現(xiàn)4>3

3. 訪問節(jié)點3的右孩子節(jié)點4，發(fā)現(xiàn)4=4儒陨，這正是要查找的節(jié)點

   
   
   image.png
   
   

   對于一個節(jié)點分布相對均衡的二叉查找樹來說花嘶，如果節(jié)點總數(shù)是n，那么搜索節(jié)點的時間復(fù)雜度就是O(logn)蹦漠，和樹的深度是一樣的椭员。這種方式正是二分查找思想。

插入

例如插入新元素5笛园，步驟如下：

1. 訪問根節(jié)點6隘击，發(fā)現(xiàn)5<6
2. 訪問節(jié)點6的左孩子節(jié)點3，發(fā)現(xiàn)5>3
3. 訪問節(jié)點3的右孩子節(jié)點4喘沿，發(fā)現(xiàn)5>4

4. 5最終會插入到節(jié)點4的右孩子位置

   
   
   image.png

二叉樹的遍歷

二叉樹闸度，是典型的非線性數(shù)據(jù)結(jié)構(gòu)，遍歷時需要把非線性關(guān)聯(lián)的節(jié)點轉(zhuǎn)化成一個線性的序列蚜印，以不同的方式來遍歷莺禁，遍歷出的序列順序也不同。
二叉樹的遍歷包括

深度優(yōu)先遍歷

所謂深度優(yōu)先窄赋，顧名思義哟冬，就是偏向于縱深，“一頭扎到底”的訪問方式忆绰。它包括：
1）前序遍歷
二叉樹的前序遍歷浩峡，輸出順序是根節(jié)點、左子樹错敢、右子樹

image.png

image.png

image.png

/**
* 樹節(jié)點
*/
public class TreeNode {
    int data;   //數(shù)據(jù)
    TreeNode leftChild;  //左孩子
    TreeNode rightChild;  //右孩子

    TreeNode(int data) {
        this.data = data;
    }
}

/**
* 二叉樹遍歷
*/
public class BinaryTree {
    TreeNode root;
    
    public void insertNode(int data) {
        root = insert(root, data);
    }

    private TreeNode insert(TreeNode node, int data) {
        //如果是空則插入第一個節(jié)點
        if(node == null) return new TreeNode(data);

        //插左邊
        if(data < node.data) {
            node.leftChild = insert(node.leftChild, data);
        }
        //插右邊
        else if(data > node.data) {
            node.rightChild = insert(node.rightChild, data);
        }
        else {
            node.data = data;
        }
        retrun data;
    }

    /*
    * 前端遍歷
    */
    public void preOrderTraveral(TreeNode node) {
        if (node == null) {
            return;
        }
        System.out.println(node.data);
        preOrderTraveral(node.leftChild);
        preOrderTraveral(node.rightChild);
    }

    /*
    * 中序遍歷
    */
    public void inOrderTraveral(TreeNode node) {
        if (node == null) {
            return;
        }
        inOrderTraveral(node.leftChild);
        System.out.println(node.data);
        inOrderTraveral(node.rightChild);
    }

    /*
    * 后序遍歷
    */
    public void postOrderTraveral(TreeNode node) {
        if (node == null) {
            return;
        }
        postOrderTraveral(node.leftChild);
        postOrderTraveral(node.rightChild);
        System.out.println(node.data);
    }

    public static void main(String[] args) {
        BinaryTree btt = new BinaryTree();
        btt.insertNode(10);
        btt.insertNode(8);
        btt.insertNode(11);
        btt.insertNode(7);
        btt.insertNode(9);
        btt.insertNode(12);

        btt.preOrderTraveral(btt.root);
        System.out.println("=====================");
        btt.inOrderTraveral(btt.root);
        System.out.println("=====================");
        btt.postOrderTraveral(btt.root);
    }
}

廣度優(yōu)先遍歷

也叫層序遍歷取逾，顧名思義，就是二叉樹按照從根節(jié)點到葉子節(jié)點的層次關(guān)系苹支，一層一層橫向遍歷各個節(jié)點砾隅。

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

/*
* 層序遍歷
*/
public void levelOrderTraversal(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<TreeNode>();

    queue.offer(root);
    while(!queue.isEmpty()){
        TreeNode node = queue.poll();
        System.out.println(node.data);
        if(node.leftChild != null) {
            queue.offer(node.leftChild);
        }
        if(node.rightChild != null) {
            queue.offer(node.rightChild);
        }
    }
}

時間復(fù)雜度

二叉查找樹的插入和查找時間復(fù)雜度為:O(logn)。
極端情況下二叉查找樹退化成鏈表苟径，時間復(fù)雜度為O(n)案站，所以需要平衡二叉查找樹。

應(yīng)用

非線性數(shù)據(jù)：菜單棘街，組織結(jié)構(gòu)蟆盐、家譜等等
線性數(shù)據(jù)：二叉查找樹
二叉查找樹是有序的承边，我們只需要中序遍歷，就可以在 O(n) 的時間復(fù)雜度內(nèi)石挂，輸出有序的數(shù)據(jù)序列博助。
二叉查找樹的性能非常穩(wěn)定，擴容很方便(鏈表實現(xiàn))

紅黑樹

平衡二叉查找樹

image.png

這種二叉查找樹就退化成了鏈表痹愚，由于樹的深度變得多了富岳，查找的效率也會大幅下降。所以需要對這種二叉樹進行自平衡拯腮，紅黑樹就是一種自平衡的二叉查找樹窖式。

紅黑樹（Red Black Tree）

除了二叉查找樹(BST)的特征外，還有以下特征：
1）每個節(jié)點要么是黑色疾瓮，要么是紅色
2）根節(jié)點是黑色
3）每個葉子節(jié)點都是黑色的空結(jié)點（NIL結(jié)點）（為了簡單期間脖镀，一般會省略該節(jié)點）
4）如果一個節(jié)點是紅色的，則它的子節(jié)點必須是黑色的（父子不能同為紅）
5）從任一結(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色結(jié)點（平衡的關(guān)鍵）
6）新插入節(jié)點默認為紅色狼电，插入后需要校驗紅黑樹是否符合規(guī)則，不符合則需要進行平衡
一顆典型的紅黑樹：

image.png

在對紅黑樹進行添加或者刪除操作時可能會破壞這些特點弦蹂，所以紅黑樹采取了很多方式來維護這些特點肩碟，從而維持平衡。主要包括：左旋轉(zhuǎn)凸椿、右旋轉(zhuǎn)和顏色反轉(zhuǎn)

左旋（RotateLeft）

逆時針旋轉(zhuǎn)紅黑樹的兩個結(jié)點削祈，使得父結(jié)點被自己的右孩子取代，而自己成為自己的左孩子

image.png

上圖所示過程如下：

1. 以X為基點逆時針旋轉(zhuǎn)
2. X的父節(jié)點被x原來的右孩子Y取代
3. c保持不變
4. Y節(jié)點原來的左孩子c變成X的右孩子

右旋（RotateRight）

順時針旋轉(zhuǎn)紅黑樹的兩個結(jié)點脑漫，使得父結(jié)點被自己的左孩子取代髓抑，而自己成為自己的右孩子

image.png

上圖所示過程如下：

1. 以X為基點順時針旋轉(zhuǎn)
2. X的父節(jié)點被x原來的左孩子Y取代
3. b保持不變
4. Y節(jié)點原來的右孩子c變成X的左孩子

顏色反轉(zhuǎn)

就是當前節(jié)點與父節(jié)點、叔叔節(jié)點同為紅色优幸，這種情況違反了紅黑樹的規(guī)則吨拍，需要將紅色向祖輩上傳，父節(jié)點和叔叔節(jié)點紅色變?yōu)楹谏耍瑺敔敼?jié)點從黑色變?yōu)榧t色（爺爺節(jié)點必為黑色羹饰，因為此前是符合紅黑樹規(guī)則的）。這樣每條葉子結(jié)點到根節(jié)點的黑色節(jié)點數(shù)量并未發(fā)生變化碳却，因此都其他樹結(jié)構(gòu)不產(chǎn)生影響

image.png

紅黑樹插入有五種情況队秩，每種情況對應(yīng)著不同的調(diào)整方法：
1）新結(jié)點（A）位于樹根昼浦，沒有父結(jié)點
直接讓新結(jié)點變色為黑色馍资，規(guī)則2得到滿足。同時关噪，黑色的根結(jié)點使得每條路徑上的黑色結(jié)點數(shù)目都增加了1鸟蟹，所以并沒有打破規(guī)則5

image.png

image.png

3）新結(jié)點（D）的父結(jié)點和叔叔結(jié)點都是紅色
兩個紅色結(jié)點B和D連續(xù)，違反了規(guī)則4戏锹。因此我們先讓結(jié)點B變?yōu)楹谏?/p>

image.png

image.png

image.png

image.png

我們以結(jié)點A為軸绍哎，做一次右旋轉(zhuǎn)来农，使得結(jié)點B成為祖父結(jié)點，結(jié)點A成為結(jié)點B的右孩子

image.png

image.png

紅黑樹構(gòu)建過程

如下圖：

image.png

上圖所示過程如下：
1）新插入節(jié)點默認為紅色海诲，5<10繁莹，插入到左子節(jié)點，插入后左子樹深度為2（葉子節(jié)點黑色+根節(jié)點黑色）特幔，右子樹深度為也是2（葉子節(jié)點黑色+根節(jié)點黑色）咨演，滿足紅黑樹規(guī)則。
2）新插入節(jié)點為紅色敬辣，9<10雪标，需要在左子樹進行插入，再和5比較溉跃，大于5村刨，放到5的右子樹中，此時各個葉子節(jié)點到根節(jié)點的深度依然是2撰茎，但5和9兩個節(jié)點都是紅色嵌牺，不滿足規(guī)則第4條，需要進行左旋、右旋操作逆粹，使其符合規(guī)則募疮。可以看出經(jīng)過操作后僻弹，左右子樹又維持了平衡阿浓。

image.png

2）繼續(xù)插入6節(jié)點钝域，對樹深度沒有影響。
3）插入7節(jié)點后锭魔，6网梢、7節(jié)點都為紅節(jié)點，不滿足規(guī)則4赂毯，需要進行顏色反轉(zhuǎn)調(diào)整，也就是7的父節(jié)點和叔叔節(jié)點變?yōu)楹谏鹪祝瑺敔敼?jié)點5變?yōu)榧t色党涕。

image.png

image.png

image.png

上圖所示過程如下：
1）插入節(jié)點17后，未破壞紅黑樹規(guī)則圆雁，不需要調(diào)整忍级。

package com.david.tree.redblack;

/**
* 紅黑樹節(jié)點
*/
public class RBTreeNode {
    private int key;
    private boolean isBlack;
    private RBTreeNode left;
    private RBTreeNode right;
    private RBTreeNode parent;

    public RBTreeNode(int key) {
        this.key = key;
        this.isBlack = false;  //新節(jié)點默認是紅色
    }

    public int getKey() {
        return key;
    }

    public boolean isBlack() {
        return isBlack;
    }

    public RBTreeNode getLeft() {
        return left;
    }

    public RBTreeNode getRight() {
        return right;
    }

    public RBTreeNode getParent() {
        return parent;
    }

    public void setKey(int key) {
        this.key = key;
    }

    public void setBlack(boolean black) {
        isBlack = black;
    }

    public void setLeft(RBTreeNode left) {
        this.left = left;
    }

    public void setRight(RBTreeNode right) {
        this.right = right;
    }

    public void setParent(RBTreeNode parent) {
        this.parent = parent;
    }

    @Override
    public String toString() {
        return "RBTreeNode{" +
               "key" + key +
               ", color=" + (isBlack == true ? "BLACK":"RED") +
               '}';
    }
}

紅黑樹實現(xiàn)

package com.david.tree.redblack;

/**
* 紅黑樹
*/
public class RBTree {
    RBTreeNode root;  //根節(jié)點

    /**
    * 遍歷節(jié)點
    *
    */
    public void list(RBTreeNode node) {
        if (node == null) return;
        //葉子
        if (node.getLeft() == null && node.getRight() == null) {
            System.out.println(node);
            return;
        }
        System.out.println(node);
        //遞歸 左孩子
        list(node.getLeft());
        //遞歸 右孩子
        list(node.getRight());
    }

    public void insert(int key) {
        RBTreeNode node = new RBTreeNode(key);
        if (root == null) {
            node.setBlack(true);   //根是黑色的
            root = node;
            return;
        }
        RBTreeNode parent = root;
        RBTreeNode son = null;
        if (key <= parent.getKey()) {
            son = parent.getLeft();
        } else {
            son = parent.getRight();
        }
        //find the position
        while (son != null) {
            parent = son;
            if (key <= parent.getKey()) {
                son = parent.getLeft();
            } else {
                son = parent.getRight();
            }
        }
        if (key <= parent.getKey()) {
            parent.setLeft(node);
        } else {
            parent.setRight(node);
        }
        node.setParent(parent);

        //自平衡
        banlanceInsert(node);
    }
    
    /**
    * 自平衡
    *
    * @param node
    */
    private void banlanceInsert(RBTreeNode node) {
        RBTreeNode father, grandFather;
        while ((father = node.getParent()) != null && father.isBlack() == false) {
            grandFather = father.getParent();
            //父為祖左孩子
            if (grandFather.getLeft() == father) {
                RBTreeNode uncle = grandFather.getRight();
                if (uncle != null && uncle.isBlack() == false) {
                    setBlack(father);
                    setBlack(uncle);
                    setRed(grandFather);
                    node = grandFather;
                    continue;
                }
                if (node == father.getRight()) {
                    //左旋
                    leftRotate(father);
                    RBTreeNode tmp = node;
                    node = father;
                    father = tmp;
                }
                setBlack(father);
                setRed(grandFather);
                //右旋
                rightRotate(grandFather);
            }
            //父為祖右孩子
            else {
                RBTreeNode uncle = grandFather.getLeft();
                if (uncle != null && uncle.isBlack() == false) {
                    setBlack(father);
                    setBlack(uncle);
                    setRed(grandFather);
                    node = grandFather;
                    continue;
                }
                if (node == father.getLeft()) {
                    //右旋
                    rightRotate(father);
                    RBTreeNode tmp = node;
                    node = father;
                    father = tmp;
                }
                setBlack(father);
                setRed(grandFather);
                //左旋
                leftRotate(grandFather);
            }
        }
        setBlack(root);
    }
}

/**
*左旋
*
* @param node
*/
private void leftROtate(RBTreeNode node) {
    RBTreeNode right = nede.getRight();
    RBTreeNode parent = node.getParent();
    if (parent == null) {
        root = right;
        right.setParent(null);
    } else {
        if (parent.getLeft() != null && parent.getLeft() == node) {
            parent.setLeft(right);
        } else {
            parent.setRight(right);
        }
        right.setParent(parent);
    }
    node.setParent(right);
    node.setRight(right.getLeft());
    if (right.getLeft() != null) {
        right.getLeft().setParent(node); 
    }
    right.setLeft(node);
}

/**
* 右旋
* 
* @param node
*/
private void rightRotate(RBTreeNode node) {
    RBTreeNode left = node.getLeft();
    RBTreeNode parent = node.getParent();
    if (parent == null) {
        root = left;
        left.setParent(null);
    } else {
        if (parent.getLeft() != null && parent.getLeft() == node) {
            parent.setLeft(left);
        } else {
            pacent.setRight(left);
        }
        left.setParent(parent);
    }
    node.setParent(left);
    node.setLeft(left.getRight());
    if (left.getRight() != null) {
        left.getRight().setParent(node);
    }
    left.setRight(node);
}

private void setBlack(RBTreeNode node) {
    node.setBlack(true);
}

private void setRed(RBTreeNode node) {
    node.setBalck(false);
}

public static void main(String[] args) {
    RBTree rb = new RBTree();
    rb.insert(10);
    rb.insert(5);
    rb.insert(9);
    rb.insert(3);
    rb.insert(6);
    rb.insert(7);
    rb.insert(19);
    rb.insert(32);
    rb.insert(24);
    rb.insert(17);
    rb.list(rb.root);
  }
}

時間復(fù)雜度：O(logn)

應(yīng)用

在JDK1.8中HashMap使用數(shù)組+鏈表+紅黑樹的數(shù)據(jù)結(jié)構(gòu)。內(nèi)部維護著一個數(shù)組table伪朽，該數(shù)組保存著每個鏈表的表頭結(jié)點或者樹的根節(jié)點轴咱。HashMap存儲數(shù)據(jù)的數(shù)組定義如下，里面存放的是Node<K,V>實體：

transient Node<K, V>[] table;//序列化時不自動保存 

/*** 桶的樹化閾值：即 鏈表轉(zhuǎn)成紅黑樹的閾值烈涮， * 在存儲數(shù)據(jù)時朴肺，當鏈表長度 > 該值時，則將鏈表轉(zhuǎn)換 成紅黑樹 */ 
static final int TREEIFY_THRESHOLD = 8;

多路查找樹

多路查找樹(muitl-way search tree)坚洽，其每一個節(jié)點的孩子數(shù)可以多于兩個戈稿，且每一個節(jié)點處可以存儲多個元素。

B樹

B樹（BalanceTree）是對二叉查找樹的改進讶舰。它的設(shè)計思想是鞍盗，將相關(guān)數(shù)據(jù)盡量集中在一起，以便一次讀取多個數(shù)據(jù)跳昼，減少硬盤操作次數(shù)般甲。

一棵m階的B 樹 (m叉樹)的特性如下：

1）B樹中所有節(jié)點的孩子節(jié)點數(shù)中的最大值稱為B樹的階，記為M
2）樹中的每個節(jié)點至多有M棵子樹 ---即：如果定了M鹅颊，則這個B樹中任何節(jié)點的子節(jié)點數(shù)量都不能超過M
3）若根節(jié)點不是終端節(jié)點敷存，則至少有兩棵子樹
4）除根節(jié)點和葉節(jié)點外，所有點至少有m/2棵子樹
5）所有的葉子結(jié)點都位于同一層

image.png

B+樹

B+樹是B-樹的變體堪伍，也是一種多路搜索樹锚烦，其定義基本與B樹相同，它的自身特是：
非葉子結(jié)點的子樹指針與關(guān)鍵字個數(shù)相同
非葉子結(jié)點的子樹指針P[i]帝雇，指向關(guān)鍵字值屬于[K[i], K[i+1])的子樹
為所有葉子結(jié)點增加一個鏈指針
所有關(guān)鍵字都在葉子結(jié)點出現(xiàn)

image.png

數(shù)據(jù)結(jié)構(gòu)和算法的可視化網(wǎng)站：

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

典型應(yīng)用

MySQL索引B+Tree
B樹是為了磁盤或其它存儲設(shè)備而設(shè)計的一種多叉（下面你會看到涮俄，相對于二叉，B樹每個內(nèi)結(jié)點有多個分支摊求，即多叉）平衡查找樹禽拔。 多叉平衡
1）B樹的高度一般都是在2-4這個高度刘离，樹的高度直接影響IO讀寫的次數(shù)。
2）如果是三層樹結(jié)構(gòu)---支撐的數(shù)據(jù)可以達到20G睹栖，如果是四層樹結(jié)構(gòu)---支撐的數(shù)據(jù)可以達到幾十T硫惕。
B和B+的區(qū)別
B樹和B+樹的最大區(qū)別在于非葉子節(jié)點是否存儲數(shù)據(jù)的問題。
B樹是非葉子節(jié)點和葉子節(jié)點都會存儲數(shù)據(jù)野来。
B+樹只有葉子節(jié)點才會存儲數(shù)據(jù)恼除，而且存儲的數(shù)據(jù)都是在一行上，而且這些數(shù)據(jù)都是有指針指向的曼氛，也就是有順序的豁辉。

二叉堆

二叉堆本質(zhì)上是一種完全二叉樹，它分為兩個類型

1. 大頂堆(最大堆)
   最大堆的任何一個父節(jié)點的值舀患，都大于或等于它左徽级、右孩子節(jié)點的值

   
   
   image.png

2. 小頂堆(最小堆)
   最小堆的任何一個父節(jié)點的值，都小于或等于它左聊浅、右孩子節(jié)點的值

   
   
   image.png
   
   

   二叉堆的根節(jié)點叫作堆頂
   最大堆和最小堆的特點決定了：最大堆的堆頂是整個堆中的最大元素餐抢；最小堆的堆頂是整個堆中的最小元素

二叉堆的存儲原理

完全二叉樹比較適合用數(shù)組來存儲。用數(shù)組來存儲完全二叉樹是非常節(jié)省存儲空間的低匙。因為我們不需要存儲左右子節(jié)點的指針旷痕，單純地通過數(shù)組的下標，就可以找到一個節(jié)點的左右子節(jié)點和父節(jié)點顽冶。

image.png

從圖中我們可以看到欺抗，數(shù)組中下標為 i 的節(jié)點的左子節(jié)點，就是下標為 i?2 的節(jié)點强重，右子節(jié)點就是下標為 i?2+1 的節(jié)點绞呈，父節(jié)點就是下標為 i/2 取整的節(jié)點。

二叉堆的典型應(yīng)用

優(yōu)先隊列
利用堆求 Top K問題
在一個包含 n 個數(shù)據(jù)的數(shù)組中间景，我們可以維護一個大小為 K 的小頂堆报强，順序遍歷數(shù)組，從數(shù)組中取出數(shù)據(jù)與堆頂元素比較拱燃。如果比堆頂元素大，我們就把堆頂元素刪除力惯，并且將這個元素插入到堆中碗誉；如果比堆頂元素小，則不做處理父晶，繼續(xù)遍歷數(shù)組哮缺。這樣等數(shù)組中的數(shù)據(jù)都遍歷完之后，堆中的數(shù)據(jù)就是前 K 大數(shù)據(jù)了甲喝。