堆树的构建与删除

50

7

20

24

新插入结点放入数组的len  位置上，数组扩展一个位置。A[len] = 50

40

21

8

25

重复上一步操作，直到21 比子结点大，或者为叶子结点结束

删除结点79

19

79

18

9

17

10

i = 2;A[i] > A[2*i+1]; falseA[i] > A[2*i + 2]; falseA[i] =  A[2*i + 1] > A[2*i + 2] ? A[2*i + 1] : A[2*i + 2]i = 2*i+1 = 5

堆树是一颗特殊的二叉树。1. 首先它是一颗完全二叉树2. 其每一个结点的值都大小等于左右子节点（大顶堆）或者小于等于左右子结点（小顶堆）

len = 6

len = 13

堆树是一颗完全二叉树可以用数组A表示： 

插入堆树末尾，再进行堆化

继续与父节点比较len = 2*i + 1 父结点位置pos = (len - 1) / 2比较交换位置： A[pos] > A[len] ? 不动：交换位置A[pos] = 50;A[len] = 40;len = pos;

插入结点50

堆化过程：插入结点和其父结点比较，如果 比父结点大交互位置，否则不用变。交换后再与交换后的父结点比较，直到不能交换为止。

将期望删除的结点和最后一个叶子结点交换位置，然后删除最后一个叶子结点

将21 这个节点从上到下做堆化和当前结点的左右结点进行比较，如果比左右结点大则不动。如果比左右结点都小，和左右结点较大的数交换。如果只比其中一个结点小，这直接和其中一个交换位置

len = 2*i + 1 父结点位置pos = (len - 1) / 2比较交换位置： A[pos] > A[len] ? 不动：交换位置A[pos] = 50;A[len] = 20;len = pos;

len = 2

i = 0;左结点： 2 * i + 1;右结点: 2*i + 2;

i = 0;A[i] > A[2*i+1]; falseA[i] > A[2*i + 2]; falseA[i] =  A[2*i + 1] > A[2*i + 2] ? A[2*i + 1] : A[2*i + 2]i = 2*i+2 = 2