1.3　左傾堆

前面介紹過堆，當(dāng)需要合并兩個(gè)堆時(shí)，往往效率較低。本節(jié)介紹的左傾堆能高效地實(shí)現(xiàn)兩個(gè)堆的合并，稱之為可并堆。左傾堆又稱為左偏樹、左偏堆、最左堆等。

1.3.1　左傾堆相關(guān)定義和性質(zhì)

零距離（Null Path Length，NPL）是指從一個(gè)節(jié)點(diǎn)到一個(gè)“最近的不滿節(jié)點(diǎn)”的路徑長(zhǎng)度。不滿節(jié)點(diǎn)是指該節(jié)點(diǎn)的左、右子節(jié)點(diǎn)至少有一個(gè)為空。葉子節(jié)點(diǎn)的NPL為0；空節(jié)點(diǎn)的NPL為-1。

在左傾堆中的每個(gè)節(jié)點(diǎn)均維護(hù)兩個(gè)值—鍵值和零距離。左傾堆滿足：

（1）節(jié)點(diǎn)的鍵值小于或等于它的子節(jié)點(diǎn)的鍵值，即堆性質(zhì)。

（2）節(jié)點(diǎn)的左子節(jié)點(diǎn)的NPL大于或等于右子節(jié)點(diǎn)的NPL，即左傾性質(zhì)。

（3）節(jié)點(diǎn)的NPL等于它的右子節(jié)點(diǎn)的NPL+1。

（4）左傾堆的任意子樹也是左傾堆。

1.3.2　左傾堆的操作

（1）兩個(gè)左傾堆的合并。將A和B兩個(gè)左傾堆合并為C，如果其中一個(gè)為空，只需返回另一棵樹即可；當(dāng)A和B都為非空時(shí)，假設(shè)A的根節(jié)點(diǎn)小于等于B的根節(jié)點(diǎn)（否則交換A、B），把A的根節(jié)點(diǎn)作為新樹C的根節(jié)點(diǎn)，然后合并A的右子樹和B，之后右子樹的NPL可能會(huì)變大，當(dāng)A的右子樹的NPL大于其左子樹的NPL時(shí)，左傾堆的左傾會(huì)被破壞。在這種情況下，只需要交換左、右子樹。最后，由于A的右子樹的NPL可能發(fā)生改變，必須更新A的NPL：NPL（A）←NPL（A的右子樹）+1。

（2）插入新節(jié)點(diǎn)。單個(gè)節(jié)點(diǎn)也可以看成一個(gè)左傾堆，因此向左傾堆插入一個(gè)節(jié)點(diǎn)可以看成兩個(gè)左傾堆的合并。

（3）刪除最小節(jié)點(diǎn)。左傾堆的根節(jié)點(diǎn)就是最小節(jié)點(diǎn)，在刪除根節(jié)點(diǎn)后，需要將兩棵子樹合并。

左傾堆的實(shí)現(xiàn)如下所述。

1.3.3　例題講解

例1-2　Financial Fraud

Time Limit:3000 ms　Memory Limit:65536 KB

題目描述：

給定一個(gè)整數(shù)序列A1,A2,…,AN，求一個(gè)非遞減序列B1,B2,…,BN（1≤i<j≤N，Bi≤Bj），使得風(fēng)險(xiǎn)值最小，即|A1-B1|+|A2-B2|+…+|AN-BN|最小。

輸入：

第一行輸入N（N≤50000），第二行輸入N個(gè)整數(shù)表示序列A（-109≤Ai≤109），N等于0時(shí)結(jié)束輸入。

輸出：

最小風(fēng)險(xiǎn)值。

樣例輸入：

4

300 400 200 100

0

樣例輸出：

400

題目來源：ZOJ3512。

解題思路：

當(dāng)A是一個(gè)非遞減序列時(shí)，只需讓Bi=Ai即可；當(dāng)A是一個(gè)非遞增序列時(shí)，最優(yōu)解是讓B1=B2=…=BN=序列A的中位數(shù)（中位數(shù)是指序列中第N/2大的數(shù)）；當(dāng)A不是以上兩種特殊情況時(shí)，可以考慮把序列A分為一些區(qū)間段，相對(duì)應(yīng)的序列B為那一段的中位數(shù)。

假設(shè)已經(jīng)找到前k個(gè)數(shù)A1,A2,…,Ak（k<N）的最優(yōu)解，需要求前k+1個(gè)數(shù)的最優(yōu)解。先把第k+1個(gè)數(shù)單獨(dú)作為一個(gè)區(qū)間，則中位數(shù)就是Ak+1，因?yàn)橐?span id="efokhia" class="emphasis_italic">B是非遞減序列，如果Ak+1大于或等于前一個(gè)區(qū)間的中位數(shù)，就保留Ak+1作為單獨(dú)一個(gè)區(qū)間；否則，需要將Ak+1和前一個(gè)區(qū)間合并。

因?yàn)樯婕皡^(qū)間合并，很容易想到本節(jié)介紹的可合并堆—左傾堆。如何用左傾堆維護(hù)區(qū)間中位數(shù)呢？只需要用大頂堆維護(hù)區(qū)間較小的一半元素，這樣堆頂元素就是中位數(shù)。在每次從左向右求解時(shí)，可把每一個(gè)數(shù)單獨(dú)建一個(gè)左傾堆，如果當(dāng)前區(qū)間的中位數(shù)小于前一個(gè)區(qū)間的中位數(shù)時(shí)，就將兩個(gè)左傾堆合并，并彈出堆頂多余的元素。

題目實(shí)現(xiàn)：