神奇的优先队列

支持插入元素和寻找最大（小）值元素的数据结构称之为优先队列。...



加微信群回复公众号：微信群；QQ群16004488

加微信群或QQ群可免费索取学习教程

堆是什么？是一种特殊的完全二叉树，就像下面这棵树一样。

有没有发现这棵二叉树有一个特点，就是所有父结点都比子结点要小（注意：圆圈里面的数是值，圆圈上面的数是这个结点的编号，此规定仅适用于本节）。符合这样特点的完全二叉树我们称为最小堆。反之，如果所有父结点都比子结点要大，这样的完全二叉树称为最大堆。那这一特性究竟有什么用呢？

假如有14个数分别是99、5、36、7、22、17、46、12、2、19、25、28、1和92。请找出这14个数中最小的数，请问怎么办呢？最简单的方法就是将这14个数从头到尾依次扫一遍，用一个循环就可以解决。这种方法的时间复杂度是O(14)也就是O(N)。

[quote]for(i=1;i

    关注 计算机与网络安全