> 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/thinking.md).

# 思考题

## 6-1 用插入方法建堆

```cpp
void Heap::Build_Max_Heap()
{
    heap_size = 1;
    //从堆中最后一个元素开始，依次调整每个结点，使符合堆的性质
    for(int i = 2; i <= length; i++)
        Max_Heap_Insert(A[i]);
}
```

答：

a）A = {1,2,3};

b）MAX-HEAP-INSERT的过程如下：

加入大小为-0x7FFFFFFF的新结点，O(1)

将该值调整为key,最坏情况下为O(lgn)

对每个结点都要执行一次插入操作，因此最坏时间为O(nlgn)

## 6-2 对d叉堆的分析

a）根结点是A\[1]，根结点的孩子是A\[2],A\[3],……，A\[d+1]

PARENT(i) = (i - 2 ) / d + 1

CHILD(i, j ) = d \* (i - 1) + j + 1

b）lgn/lgd

c）HEAP-EXTRACR-MAX(A)与二叉堆的实现相同，其调用的MAX-HEAPIFY(A, i)要做部分更改，时间复杂度是O(lgn/lgd \* d)

```
MAX-HEAPIFY(A, i)
1    largest <- i
2    for j <- 1 to d
3        k <- CHILD(i, j)  
4        if k <= heap-size[A] and A[k] > A[largest]  
5            largest <- k
6    if largest != i  
7    then exchange A[i] <-> A[largest]  
8             MAX-HEAPIFY(A, largest)
```

d）和二叉堆的实现完全一样，时间复杂度是O(lgn/lgd)

e）和二叉堆的实现完全一样，时间复杂度是O(lgn/lgd)


---

# 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:

```
GET https://windmising.gitbook.io/introduction-to-algorithms/introduction/thinking.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
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.