| 共 44 篇文章 |
|
}protected void merge(Node u, int i, Node v, Node w) {Utils.myassert(v.id == u.children[i]);}}}/** * Shift keys from node v into node w * @param u the parent of v and w * @param i the index w in u.children * @param v the left sibling of w * @param w the right sibling of v */protected void shiftRL(Node u, int i, Node v... 阅94 转0 评0 公众公开 15-01-15 09:54 |
binary serachpublic int size() {//hi 高位,lo 低位int lo = 0, hi = keys.length;while (hi != lo) {int m = (hi+lo)/2;if (keys[m] == null) {h = m;}else {lo = m+1;}return lo;}} 阅82 转0 评0 公众公开 15-01-13 11:00 |
倒排索引有两种不同的反向索引形式： 一条记录的水平反向索引（或者反向档案索引）包含每个引用单词的文档的列表。一般在文档集合里会有很多文档包含某个单词，每个文档会记录文档编号（DocID），单词在这个文档中出现的次数（TF）及单词在文档中哪些位置出现过等信息，这样与一个文档相关的信息被称做倒排索引项（Posting），包含这个... 阅166 转0 评0 公众公开 14-05-14 15:02 |
位图主要用于快速检索关键字状态，通常要求关键字是一个连续的序列（或者关键字是一个连续序列中的大部分）， 最基本的情况，使用1bit标示一个关键字的状态（可标示两种状态），但根据需要也可以使用2bit（标示4种状态），3bit（标示8种状态），当一个状态标示需要的位数达到32bit时，就演变成来一个整型数组了。解法：从0~20亿，为每个QQ号分... 阅70 转0 评0 公众公开 14-05-08 00:38 |
Bloom Filter应用之Web Cache Sharing.为了减少带宽使用、降低web server的负载，我们常常通过代理服务器（proxy）浏览网页，浏览过的网页会被cache在proxy中，如果有别的请求或者下一次访问相同的网页，proxy就不用将请求转给web server，而是直接将本地cache的网页返回。因此它希望将proxy中cache的内容用简洁的形式表示（cache summary），... 阅42 转1 评0 公众公开 14-05-08 00:15 |
这样又出现只含有一个元素F结点的情况，这时，其相邻的兄弟结点是丰满的（元素个数为3>最小元素个数2），这样就可以想父结点借元素了，把父结点中的J下移到该结点中，相应的如果结点中J后有元素则前移，然后相邻兄弟结点中的第一个元素（或者最后一个元素）上移到父节点中，后面的元素（或者前面的元素）前移（或者后移）；D4：[缩减树] 当... 阅60 转0 评0 公众公开 14-05-07 23:05 |
B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与... 阅50 转自Home of h... 公众公开 14-05-07 23:03 |
阅539 转3 评0 公众公开 14-05-07 22:32 |
二叉堆根据根结点与其子结点的大小比较关系，分为最大堆和最小堆。2.2.2、MAX-HEAPIFY的运行时间 MAX-HEAPIFY作用在一棵以结点i为根的、大小为n的子树上时，其运行时间为调整元素A[i]、A[LEFT(i)]，A[RIGHT(i)]的关系时所用时间为O(1)，再加上，对以i的某个子结点为根的子树调用MAX-HEAPIFY所需的时间，且i结点的子树大小至多为2n/3，所以，M... 阅342 转2 评0 公众公开 14-05-07 19:56 |
同时我们知道序号为（n/2+1）~n的元素都是叶子节点（因为其子女节点的序号都大于n，即说明没有子女节点），因此我们构建最大堆的操作就在序号为1~n/2的元素内进行（其他元素已满足最大堆性质）。其操作内容如下：对于每个节点i，我们考察他与子女节点的大小，如果他比某个子女节点小，则将他与子女节点中最大的那个互换位置，然后在相应的子女... 阅14795 转135 评0 公众公开 14-05-07 19:51 |
