【データ構造とアルゴリズム】二叉スタック

コアオペレーションはsift_up,sift_down、他のすべての操作はこの2つのコア操作に基づいて構築されており、実際にはすべてのスタック構造がこの2つの操作を使用することができます.

const int maxsize = 10001;
int size = 0;
int min_heap[maxsize];/*0      ，      0  ， k/2        */


void sift_up(int k)//  k     ，      
{
	int tmp = min_heap[k];
	for(; k>1;k=k>>1 )/*       ,     k              */
	{
		if(tmp < min_heap[k>>1])
			min_heap[k] = min_heap[k>>1];
		else break;
	}
	min_heap[k] = tmp;
}


void sift_down(int k)//  k     ，      
{
	int tmp = min_heap[k];
	for(k=k<<1; k<=size; k=k<<1)/*          ，  k    k>>1             */
	{
		if(k+1<=size && min_heap[k+1] < min_heap[k])/*       */
			++k;		
		if(tmp > min_heap[k])
			min_heap[k>>1] = min_heap[k];
		else	break;		
	}
	min_heap[k>>1] = tmp;
}


/*  */
void push(int x)/*    x*/
{
	min_heap[++size] = x;
	sift_up(size);
}

/*  */
/******
       pop                 ，
         ，  pop          
*******/

void pop(int k=1)/*    k     ，1     */
{
	min_heap[k] = min_heap[size--];/*      k  */
	sift_up(k);
	sift_down(k);
}
int getTop()
{
	int top = min_heap[1];
	pop(1);
	return top;
}
/*  */
void update(int k,int x)/*  k            x*/
{
	min_heap[k] = x;
	sift_up(k);
	sift_down(k);
}