# 1.4.2 Heap Tree

## 定義:

## 最小堆積(Min heap):父節點若小於子節點, 則稱之.

## 最大堆積(Max heap):父節點若大於子節點, 則稱之.

(然而, 同一層的子節點則無須理會其大小關係)

一個堆積樹必定為完整二元樹(complete binary tree), 且通常會用陣列來實作.

所以大概長得像這樣(Min heap):

```
                            10 -> s
                            / \
                           /   \              s(parent), 2s(left), 2s+1(right)為節點在陣列中的索引關係
                          /     \                  
                         /       \ 
                        /         \
                       25 ->2s     15 ->2s+1
                     /   \        / \
                    30    26     20 29
                   /  \   / \    /
                  35  40 27 28  22
```

再來要知道怎麼建立堆積樹, 此處以上圖的min heap為例:

假設此處以一維陣列來儲存這棵樹, 現在要加入一個元素(12)

1. 首先, 新加入的元素會被放到最後的葉節點

   ```
                        10
                        / \
                       /   \
                      /     \
                     /       \ 
                    /         \
                   25          15
                 /   \        / \
                30    26     20 29
               /  \   / \    / \
              35  40 27 28  22  12 <---這裡
   ```
2. 然後新加入的節點會跟父節點做比對, 若小於父節點則往上升, 直至滿足堆積樹的條件為止才停下來

   ```
                        10
                        / \
                       /   \
                      /     \
                     /       \ 
                    /         \
                   25          15
                 /   \        / \
                30    26     12 29
               /  \   / \    / \
              35  40 27 28  22  20

                        10
                        / \
                       /   \
                      /     \
                     /       \ 
                    /         \
                   25          12 <---上不去惹
                 /   \        / \
                30    26     15 29
               /  \   / \    / \
              35  40 27 28  22 20
   ```

建立好堆積樹之後, 樹根一定是所有元素的最小值, 排序應用時:

1. **將最小值取出**
2. **調整樹為最小堆積樹**

不斷重複以上步驟就可達到排序的效果了, 其中, 取出最小值的做法是**將樹根與最後一個葉節點做交換,然後切下葉節點**, 並重新調整為堆積樹, 在這段過程中, 找出父節點跟兩個子節點中較小的一個做交換:

```
1. 將最小值取出(跟最後一個葉節點交換)

                     20 <---換到最上面
                     / \
                    /   \
                   /     \
                  /       \ 
                 /         \
                25          12
              /   \        / \
             30    26     15 29
            /  \   / \    / \
           35  40 27 28  22 10 <---被換下來了

2.將最小值取出(拿出來)

                     20
                     / \
                    /   \
                   /     \
                  /       \ 
                 /         \
                25          12
              /   \        / \
             30    26     15 29
            /  \   / \    /
           35  40 27 28  22 

           -> 10

3. 開始調整直到變成堆積樹

                     12
                     / \
                    /   \
                   /     \
                  /       \ 
                 /         \
                25         15
              /   \        / \
             30    26     20 29
            /  \   / \    / \_________>它往下換兩次後就停住了
           35  40 27 28  22 

           -> 10
```

因為此處假設使用一維陣列來儲存堆積樹, 所以一直重複此步驟的話, 每次將葉節點跟最小值交換的動作就是把最小值放到陣列的後端, 所以到最後陣列就變成排序好的狀態了.

## 整理:

堆積樹建立的過程(insert): 氣泡排序(樹葉到樹根), O(logn)

調整過程: 氣泡排序(樹根到樹葉), O(logn)

取出最大/小值: 直接拿根節點, Θ(1)

堆積排序法(Heap Sort)又被稱為**改良的選擇排序法**

・Best Case: O(nlogn)

・Worst Case: O(nlogn)

・Average Case: O(nlogn)

說明：

建立MaxHeap： Ο(n)

執行n-1次Delete Max：(n-1) × Ο(log n) = Ο( n log n)

・合併兩個Heap Tree: 最優方法是把兩個heap tree首尾相連放在一個陣列中, 然後構造新的heap tree. 時間複雜度為O(logn\*logk), 其中n、k為兩個heap tree的元素數目.

* 範例程式: [點我](https://github.com/yotsuba1022/LeetCode/blob/master/src/main/java/idv/carl/datastructures/heaptree/MaxHeap.java)


---

# Agent Instructions: 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://clu.gitbook.io/data-structure-note/heap-tree.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.