二叉堆和二叉搜尋樹進階

1、引言

《算法競賽進階指南》中指出，在二叉樹中，有兩組非常重要的條件，分别是兩類資料結構的基本性質。

其一是“堆性質”，若二叉樹中的任意一個節點的權值都大于等于（小于等于）其父親節點，則稱該二叉樹滿足“小頂堆性質（大頂堆性質）”。

其二是“BST性質”，二叉樹上的每個節點都帶有一個數值，稱為該節點的鍵值 $key$，樹中的任意一個節點的 $key$ 均同時滿足：大于等于其左子樹中任意節點的 $key$，小于等于其右子樹中任意節點的 $key$。

在日常的刷題過程中，經常會用到優先隊列、set、map等STL的容器，但是實際上它們的底層實作某種程度上可以說是二叉堆或者BST，而且二叉堆和BST作為較基礎的資料結構，我們應當學會如何實作。

2、二叉堆的實作

struct Heap
{
    int sz;
    int heap[maxn];
    void up(int now)
    {
        while(now>1)
        {
            int par=now>>1;
            if(heap[now]<heap[par]) //子節點小于父節點，不滿足小頂堆性質
            {
                swap(heap[par],heap[now]);
                now=par;
            }
            else break;
        }
    }
    void push(int x) //插入權值為x的節點
    {
        heap[++sz]=x;
        up(sz);
    }
    inline int top(){return heap[1];}
    void down(int now)
    {
        while((now<<1)<=sz)
        {
            int nxt=now<<1;
            if(nxt+1<=sz && heap[nxt+1]<heap[nxt]) nxt++; //取左右子節點中較小的
            if(heap[now]>heap[nxt]) //子節點小于父節點，不滿足小頂堆性質
            {
                swap(heap[now],heap[nxt]);
                now=nxt;
            }
            else break;
        }
    }
    void pop() //移除堆頂
    {
        heap[1]=heap[sz--];
        down(1);
    }
    void del(int p) //删除存儲在數組下标為p位置的節點
    {
        heap[p]=heap[sz--];
        up(p), down(p);
    }
    inline void clr(){sz=0;}
};      

3、二叉堆的應用

　　3.1、​​POJ 1456​​

　　3.2、​​二叉堆優化Dijkstra​​

　　3.3、​​BZOJ 1150​​

4、二叉搜尋樹

普通的二叉搜尋樹每次期望複雜度為 $O(\log n)$，但是非常容易退化為 $O(n)$，是以實際應用中一般使用平衡二叉查找樹。

4.1、伸展樹Splay

　　伸展樹原理：

　　　　​​伸展樹（Splay Tree）進階 - 從原理到實作​​

　　伸展樹實作：

　　　　​​POJ 3580 - SuperMemo - [伸展樹splay]​​

4.2、Treap

　　​​BZOJ 3224 - 普通平衡樹 - [Treap]​​

 ​