ElementType
DeleteMin( PriorityQueue H )
{
int i, Child;
ElementType MinElement, LastElement;
/* 1*/ if( IsEmpty( H ) )
{
/* 2*/ Error( "Priority queue is empty" );
/* 3*/ return H->Elements[ 0 ];
}
/* 4*/ MinElement = H->Elements[ 1 ];
/* 5*/ LastElement = H->Elements[ H->Size-- ];
/* 6*/ for( i = 1; i * 2 <= H->Size; i = Child )
{
/* Find smaller child */
/* 7*/ Child = i * 2;
/* 8*/ if( Child != H->Size && H->Elements[ Child + 1 ]
/* 9*/ < H->Elements[ Child ] )
/*10*/ Child++;
/* Percolate one level */
/*11*/ if( LastElement > H->Elements[ Child ] )
/*12*/ H->Elements[ i ] = H->Elements[ Child ];
else
/*13*/ break;
}
/*14*/ H->Elements[ i ] = LastElement;
/*15*/ return MinElement;
}
/* END */
uj5u.com熱心網友回復：
這里 N 就是 H->Size。最壞的情況：i=1，然后 Child++ 一路到底。復雜度 O(N)
最好情況：不需要 Child++，每次都 *2 前進。復雜度 O(log N)
看 Child = i * 2 這似乎是一個二叉樹，但是 /* 8..23 */ 根本沒有按二叉樹進行操作。
本來應該是固定的 O(log N) 復雜度。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/63937.html
標籤：網絡編程
上一篇：vb.net顯示最新的10張圖片