题目内容
（请给出正确答案）
在多叉堆(d-heap)中，每个节点至多可拥有d≥3个孩子，且其优先级不低于任一孩子。
a)试证明，多叉堆decrease()接口的效率可改进至O(logdn);(当然，delMax()接口的效率因此会降至O(d-logn))。
b)试证明，若取d=e/n+2，则基于d叉堆实现的Prim算法的时间复杂度可降至O(e·logdn);
c)这种改进策略是否也适用于Dijkstra算法？
如果结果不匹配，请 联系老师 获取答案
更多“在多叉堆（d-heap)中，每个节点至多可拥有d≥3个孩子，…”相关的问题
A.增加youngobject在堆中的空间
B.调整-verbosegcflagon
C.在域中增加更多的server
D.每个machine运行更多的server
四叉树(quadtree)是2d-树的简化形式，其简化策略包括：
①直接沿区域的(水平或垂直)平分线切分，从而省略了中位点的计算;
②沿垂直方向切出的每一对节点(各自再沿水平方向切分)都经合并后归入其父节点;
③被合并的节点即便原先(因所含输入点不足两个)而未继续切分，在此也需要强行(沿水平方向)切分一次。
于是如图x8.8所示，每个叶节点各含0至1个输入点;每个内部节点则都统一地拥有四个孩子，分别对应于父节点所对应矩形区域经平均划分之后所得的四个象限，该树也由此得名。
a)与kd-树不同，四叉树可能包含大量的空(即不含任何输入点的)节点。更糟糕的是，此类节点的数目无法仅由输入规模n界定。对于任意的N＞0，试构造一个仅含n=3个点的输入点集，使得在其对应的四叉树中，空节点的数目超过N个。
b)对于任一输入点集P，若将其中所有点对的最长、最小距离分别记作D和d，则λ=D/d称作P的散布度(spread)，试证明，P所对应的四叉树高度为o(logλ)。
c)试基于四叉树结构设计相应的范围查询算法，并利用你的四叉树结构实现该算法。
d)针对范围查询这一应用，试分别从时间、空间效率的角度，将四叉树与2d-树做一比较。
a)经如此转换之后，父子节点各自在物理上所对应的秩之间的换算关系，应如何调整？
b)如此改进之后，insert()和delMax()操作的时间复杂度有何变化？总体效率呢？
c)对于不易甚至无法定义最大值的元素类型(比如长度任意的字符串)，以上技巧是否依然适用？
A.在同一节点由一对不同方向的斜桩组成的基桩
B.在同一节点中由两对不同方向的叉桩组成的基桩组
C.在同一节点由一对相同方向的斜桩组成的基桩
D.在同一节点中由两对相同方向的叉桩组成的基桩组
