左偏樹

可并堆，就是支持合并，并且滿足堆性質的二叉樹，先不管如何來實現合并，假設我們已經維護好了這樣的數據結構，如何來實現堆應該有的操作: 插入:插入一個節點可以看成把一個單個節點的堆(單點顯然滿足堆性質)和堆進行合并 刪除根:可以看成把根的左子樹和右子樹合并 所以，可并堆只需要一個操作:合并，就可以實現所有堆應該有的操作。 左偏樹: 左偏樹最重要的性質正如它的名字——它是左偏的，也就是說，左偏樹的任意節點都滿足它的左子樹的節點個數小于右子樹的節點個數，這個性質有什么用呢?如果我們從根節點開始，不停的遞歸右子樹，次數一定小于log2(n),因為每次遞歸右子樹，由于右子樹的節點個數一定小于左子樹，可以看成節點個數/2。 這個性質對于合并就有很大的好處，由于這個性質，合并時只要不停的用右子樹去合并，單次合并的復雜度就可以看成是log2(n)的。 合并: 合并時，考慮將樹x和樹y合并，顯然，合并后的樹的根節點一定是兩個樹的根節點中值較小的那個，為了方便操作，默認將樹x的根節點作為根，也就是說，每次都把y與x的右子樹合并，y與x的右子樹合并后的根節點就是樹x的右兒子，還要滿足左偏性質，如果合并后右子樹的節點個數大于左子樹的節點個數，就交換左右子樹，最后更新當前子樹的大小。 代碼如下：

下面來看一道題目（摘自洛谷）： 一開始有N個小根堆，每個堆包含且僅包含一個數。接下來需要支持兩種操作：

操作1： 1 x y 將第x個數和第y個數所在的小根堆合并（若第x或第y個數已經被刪除或第x和第y個數在用一個堆內，則無視此操作）

操作2： 2 x 輸出第x個數所在的堆最小數，并將其刪除（若第x個數已經被刪除，則輸出-1并無視刪除操作）

這題顯然就是左偏樹的模板題，但是有一點需要注意，在實際運用中，左偏樹還需要維護每個節點所在的堆的堆頂，馬上就會想到并查集來維護，但是，刪除操作怎么辦?并查集并不天然支持刪除某個節點，好在這題只需要刪除堆頂就可以，顯然，合并操作時只要將需要合并的兩個堆的fa中將要作為兒子節點的fa修改為最終的根節點就可以。 但是，刪除一個節點要如何辦到？由于刪除一個根節點后可能成為根節點的只有兩個——它的兩個兒子，所以，只要把會成為新的根節點的fa更新為它自己，再把原來的根節點的fa修改為新的根節點即可。 代碼如下：

其中的vis是用來標記某個節點是否被刪除。 本題代碼：