From f08807f4d4ce5bd94183a03603c88ede38824953 Mon Sep 17 00:00:00 2001 From: 24OI-bot <15963390+24OI-bot@users.noreply.github.com> Date: Mon, 19 Oct 2020 12:56:46 -0400 Subject: [PATCH] style: format markdown files with remark-lint --- docs/ds/pairing-heap.md | 24 ++++++++++++------------ 1 file changed, 12 insertions(+), 12 deletions(-) diff --git a/docs/ds/pairing-heap.md b/docs/ds/pairing-heap.md index d22b6b56..c814586f 100644 --- a/docs/ds/pairing-heap.md +++ b/docs/ds/pairing-heap.md @@ -76,7 +76,7 @@ Node* merges(Node* x) { 1. `merge(x,a)` “配对”了 x 和 a。 2. `merges(b)` 递归合并 b 和他的兄弟们。 -3. 将上面 2 个操作产生的 2 个新树合并。 +3. 将上面 2 个操作产生的 2 个新树合并。 需要注意到的是,上文提到了配对方向和合并方向是有要求的(从左往右配对,从右往左合并),该递归函数的实现已保证了这个顺序,如果读者需要自行实现迭代版本的话请务必注意保证该顺序,否则复杂度将失去保证。 @@ -88,9 +88,9 @@ Node* delete_min(Node* x) { return merges(x->ch); } #### 减小一个元素的值 -要实现这个操作,需要给节点添加一个 father 指针,会使实现变得相对复杂。 +要实现这个操作,需要给节点添加一个 father 指针,会使实现变得相对复杂。 -其中father指针指向前一个节点而非树形结构的父节点 +其中 father 指针指向前一个节点而非树形结构的父节点 首先节点的定义修改为: @@ -113,8 +113,8 @@ Node* merge(Node* a, Node* b) { a->fa = nullptr; b->fa = nullptr; // 新增:维护fa指针 b->xd = a->ch; - if (a->ch != nullptr) //判断a的子节点是否为空 否则会空指针异常 - a->ch->fa = b; + if (a->ch != nullptr) //判断a的子节点是否为空 否则会空指针异常 + a->ch->fa = b; a->ch->fa = b; // 新增:维护fa指针 a->ch = b; return a; @@ -127,13 +127,13 @@ Node* merge(Node* a, Node* b) { Node* merges(Node* x) { x->fa = nullptr; // 新增:维护fa指针 if (x == nullptr || x->xd == nullptr) return x; - Node *a = x->xd; - Node*b = nullptr; + Node* a = x->xd; + Node* b = nullptr; if (a != nullptr) { - b = a->xd; - x->xd = a->xd = nullptr; + b = a->xd; + x->xd = a->xd = nullptr; } else { - x->xd = nullptr; + x->xd = nullptr; } a->fa = nullptr; // 新增:维护fa指针 return merge(merge(x, a), merges(b)); @@ -148,7 +148,7 @@ Node* merges(Node* x) { ```cpp // root为堆的根,x为要操作的节点,v为新的权值,调用时需保证x->v>=v // 返回值为新的根节点 -Node* decrease-key(Node* root, Node* x, LL v) { +Node* decrease - key(Node* root, Node* x, LL v) { x->v = v; // 修改权值 if (x->fa == nullptr) return x; // 如果x为根,就不用接下去的步骤了。 // 把x从fa的子节点中剖出去,这里要分x的位置讨论一下。 @@ -170,7 +170,7 @@ Node* decrease-key(Node* root, Node* x, LL v) { ### 参考文献 1. [HOOCCOOH 的题解](https://hooccooh.blog.luogu.org/solution-p3377) -2. [集训队论文《黄源河 -- 左偏树的特点及其应用》](https://wenku.baidu.com/view/20e9ff18964bcf84b9d57ba1.html) +2. [集训队论文《黄源河 -- 左偏树的特点及其应用》](https://wenku.baidu.com/view/20e9ff18964bcf84b9d57ba1.html) 3. [《配对堆中文版》](https://wenku.baidu.com/view/f2527bc2bb4cf7ec4afed06d.html) 4. [维基百科 pairing heap 词条](https://en.wikipedia.org/wiki/Pairing_heap) 5. -- 2.11.0