可并堆

可并堆有三種常見方法：斜堆，左偏樹，隨機堆我們分別聊聊這三種堆吧！

斜堆

斜堆的構建其實是和二叉堆差不多的，它只是用鏈表來維護關系罷了，這是構建代碼:

struct Heap
{
    Heap *lson, *rson;
    int val;
    Heap(int n = 0)
    {
        val = n;
        lson = rson = 0;
    }
};

然后，可并堆可并堆，最重要的是合并吧，合并怎么做呢，就是假設有兩個斜堆，將其權值比較大的斜堆插在權值比較小的斜堆的右子樹之下，但是如果只這樣的話，時間復雜度就會退化到 \(O(n)\) 的，我們只要將左子樹和右子樹交換一下 這樣子的左右子樹就比較均勻啦！，時間復雜度就講到 \(O(log_n)\) 啦，代碼如下：

Heap* merge(Heap*& a, Heap*& b)
{
    if(a == 0) return a;
    if(b == 0) return b;
    if(a -> val > b -> val) swap(a, b);
    a -> rson = merge(a -> rson, b);
    swap(a -> lson, a -> rson);
    return a;
}

剩下的就和二叉堆差不多了，代碼如下：

void Heap_insert(Heap*& a, int val)//插入
{
    Heap* b = new Heap(val);
    a = merge(a, b);
}

int Top(Heap*& a)//求最小
{
    int val = a -> val;
    return val;
}

void Del(Heap*& a)//刪最小
{
    a = merge(a -> lson, a -> rson);
}

紅黑樹和隨機堆就沒有那么簡單了。

你會發現，雖然你將左子樹和右子樹調換了從而減少了常數，但是你沒法保證這調換完之后一定左子樹比右子樹來的重呀，所以還是時間復雜度很大滴，但是欸，我們可以存一個值，表示該子樹的大小呀，這不就好了嘛。。所以，左偏樹誕生了！

左偏樹

基本結構與斜堆一樣，只是左偏樹的每個結點多了一個距離值NPL即該結點一直向右兒子走，到達空結點的距離。
構建還是和斜堆很像，代碼如下：

struct Heap
{
    Heap* lson;
    Heap* rson;
    int VAL, npl;
    Heap(int n = 0)
    {
        val = n;
        npl = 1;
        lson = 0;
        rson = 0;
    }
};

接下來依然是合并，維護了 \(npl\) 之后，我們就不用再亂交換了，而且保證了左兒子大于右兒子的\(npl\) ，效率就會提升。

那么怎么維護 \(npl\) 呢？我們來看看新的\(Merge\)：

Heap* Merge(Heap*& a, Heap*& b)
{
	if(a == 0) return b;
	if(b == 0) return a;
	if(a -> val > b -> val) swap(a, b);
	a -> rson = Merge(a -> rson, b);
	if(!a -> lson || a -> lson -> npl < a -> rson -> npl) swap(a -> lson, a -> rson);
	if(!a -> rson) a -> npl=0;
	else a -> npl = a -> rson -> npl + 1;
	return a;
}

下面是注解
首先，如果左右子樹為空，直接返回另一個
第二，如果左子樹的 \(npl\) 比較小，交換后使右子樹的高度變小,再合并。
合并后維護 \(npl\)，如果右子樹為空，\(npl\) 為\(0\)，否則為右子樹的 \(npl++\)。

剩下的就都差不多了，代碼如下：

void Heap_insert(Heap*& root,int k)
{
	Heap* n = new Heap(k);
	root = Merge(root,n);
}
int Top(Heap*& root)
{
	return root -> val;
}
void del(Heap*& root)
{
	root = Merge(root -> lson, root -> rson);
}

隨機堆

其實我們有另一種方法，欸，就是隨機，我們可以通過隨機數的奇偶來決定這次要不要交換，這樣子的話就能比一直交換的常數來的小，剩下的重要點前面都已經講過啦！所以就只放全部代碼了：

struct Heap
{
	Heap* lson;
	Heap* rson;
	int val;
	Heap(int n = 0)
	{
		val = n;
		lson = 0;
		rson = 0;
	}
}*root;

Heap* Merge(Heap*& a,Heap*& b)
{
	if(a == 0) return b;
	if(b == 0) return a;
	if(a -> val > b -> val) swap(a,b);
	if(rand() & 1) a -> rson = Merge(a -> rson, b);
	else a -> lson = Merge(a -> lson, b);
	return a;
}
void Heap_insert(Heap*& root,int k)
{
	Heap* n = new Heap(k);
	root = Merge(root, n);
}

int Top(Heap*& root)
{
	return root -> val;
}

void del(RandHeap*& root)
{
	root = Merge(root -> lson, root -> rson);
}

我這里用的是 \(rand()\) 常數超級大，大家可以換成其他的隨機數生成方式。

小結

這三種可并堆的優缺點各不相同，雖然普遍都是用左偏樹，但是其他的也要學呀，要不然他為什么要存在呢？

例題

# P11833 [省選聯考 2025] 推箱子

呃，就直接放個用可并堆打的的文章吧，在這

還有關于題單，找了好久，終于在半個月后找到了。。。。