# 二叉堆

算法 空间 平均 最差 ${\displaystyle O(n)}$ ${\displaystyle O(n)}$ ${\displaystyle O(n)}$ ${\displaystyle O(n)}$ ${\displaystyle O(1)}$ ${\displaystyle O(\log n)}$ ${\displaystyle O(1)}$ ${\displaystyle O(1)}$ ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)}$

## 存储

```            1                                 11
/      \                          /      \
2         3                       9         10
/    \     /   \                   /   \     /    \
4      5   6     7                5      6   7      8
/ \    / \                        / \    / \
8  9   10 11                      1   2  3   4
```

```位置:  1  2  3  4  5  6  7  8  9 10 11

```

## 基本操作

### 删除根节点

Max-Heapify[1] (A, i):
left ← 2i
right ← 2i + 1
largesti
if leftheap_length[A] and A[left] > A[largest] then:
largestleft
if rightheap_length[A] and A[right] > A[largest] then:
largestright
if largesti then:
swap A[i] ↔ A[largest]
Max-Heapify(A, largest)

### 构造二叉堆

Build-Max-Heap[1] (A):
heap_length[A] ← length[A]
for ifloor(length[A]/2) downto 1 do
Max-Heapify(A, i)

## 参考文献

1. Cormen, T. H. & al., Introduction to Algorithms 2nd, Cambridge, Massachusetts: The MIT Press, 2001, ISBN 0-07-013151-1
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 15, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}