左スタックマージの実装


 , !
//define the leftist heap struct
typedef struct Leftist pLeftist;
struct Leftist{

	int element;
	pLeftist left, right;
	int npl;
};

//build the merged leftist heap and return it
pLeftist BuildHeap(LeftistQueue q){

	Leftist h1, h2;

	while(!IsEmpty(q)){
		h1 = Dequeue(q);
		if(IsEmpty(q))
			return h1;		//the leftist heap has been built
		h2 = Dequeue(q);

		Enqueue(q, Merge(h1, h2));	//enqueue the new merged leftist heap
	}

	return NULL;	//there is no leftist heap in queue
}

pLeftist Merge(Leftist h1, Leftist h2){

	if(!h1)
		return h2;
	if(!h2)
		return h1;	

	if(h1->elementelement)		//compare the element and choose the root
		return MergeHeap(h1, h2);
	else
		return MergeHeap(h2, h1);
}

pLeftist MergeHeap(Leftist h1, Leftist h2){

	if(!h1->left){
		h1->left = h2;		//single node
	}else{
		h1->right = Merge(h1->right, h2);
		if(h1->left->nplright->npl)	//make left child's npl >= right's
			SwapChl(h1);
		h1->npl = h1->right->npl+1;		//make the npl equalling its right child+1
	}

	return h1;	//return the root
}

左スタックの場合、小根スタックより
1.連結速度が速く、O(n)
2.チェーンテーブルは配列よりも多くのオーバーヘッドをもたらし、複数のドメイン(npl)
3.コードは比較的複雑で、実は複雑ではありません
leftist heapに比べてskew heapがあり、合併するたびに左右に交換します.(npl)は必要ありません.データがランダムであれば、いい選択です.
ある学生はスタックの要素をランダムに削除すると言っています.このような方法がいいです.
変更点の値を負にして無限にし、上部に泡を立てて上部を削除し、残りの2つのサブツリーをマージします.
ただし、スタックはノードをランダムに削除するために使用されていないようです.一般的に削除が最も小さいことを指して、以前1つのテーマに出会ったことがあって、最も小さい3つの要素の中で1つの特定のものを削除して、このように前の3階で探して(7つの要素の中であるべきです)、それから削除して、ランダムにその中の任意のノードを削除して損をしません.
また,任意のノードを削除し,そのサブツリーを結合し,結合して得られた新しいツリーの根を元の削除ノードの位置に戻すのは合理的ではないか,なぜ最上部に泡を立てるのか.