DeleteMin (PriorityQueue H)
{
Int I, Child;
ElementType MinElement LastElement;
/* 1 */if (IsEmpty (H))
{
/* 2 */Error (" Priority queue is empty ");
/* 3 */return H - & gt; Elements [0].
}
/* */MinElement=4 H - & gt; Elements [1].
/* */LastElement=5 H - & gt; Elements (H - & gt; the Size -];
/* 6 */for (I=1; I * 2 & lt;=H - & gt; Size; I=Child)
{
/* Find smaller child */
/* seven */Child=I * 2;
/* 8 */if (Child!=H - & gt; The Size & amp; & H - & gt;
Elements Child + [1]/* 9 */& lt; H - & gt; Elements [Child])
/* 10 */Child++;
/* Percolate one level */
/* */if 11 (LastElement & gt; H - & gt; Elements [Child])
/* */H - 12 & gt; Elements [I]=H - & gt; Elements (Child);
The else
/* */break;
}
/* */H - 14 & gt; Elements [I]=LastElement;
/* 15 */return MinElement;
}
END/* */
CodePudding user response:
Here N is H - & gt; The Size,In the worst case: I=1, then Child++ all the way to the end, the complexity of O (N)
Best case: don't need Child++, * 2 to go forward, every time complexity O (log N)
See a Child=I * 2 it seems like a binary tree, but the/* 8.. 23 */no operation according to binary tree,
It should have been fixed complexity of O (log N),