> For the complete documentation index, see [llms.txt](https://windmising.gitbook.io/introduction-to-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://windmising.gitbook.io/introduction-to-algorithms/introduction-6/exercise.md).

# 练习题

## 20.1斐波那契堆

## 20.2可合并堆

### 20.2-1

### 20.2-4

McGee和FibHeap的区别在于合并的时机。\
Fibheap认为合并调整应该尽量地推迟，而McGee则在每次堆中结点有增加的时候就作合并调整。\
个人认为，合并调整操作的意义是防止堆过宽而影响性能。但是从算法过程上看，根结点的个数多少不会影响INSERT和UNION的性能，因此没有必要。\
比较认可FibHeap的做法。

## 20.3减小一个关键字与删除一个结点

### 20.3-1

根据P300的描述，只有非根结点才可能被打上标记，如果根结点有标记，一定是它是非根结点的时候打上标记，然后被移到根结点的位置。\
把结点移至根结点是通过上面代码中的函数addNodeToRootList和addListToRootList完成的，目标缩小至这两个函数周围\
让根结点成为有标记结点，须满足以下两个条件\
（1）调用这两个函数前，该结点是非根结点\
（2）调用后没有清标记\
结论：x是pMinData的孩子，根据P300的步骤被打上标记后，执行extract()时又成为根结点

## 20.4最大度的界


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://windmising.gitbook.io/introduction-to-algorithms/introduction-6/exercise.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.