堆树的构建与删除
2024-04-07 10:27:44 24 举报数据结构—堆树的构建与删除
作者其他创作
大纲/内容
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
0 条评论
下一页
