UC知道pascal牛人们 有个堆的问题
来源：百度知道 编辑：UC知道 时间：2024/05/26 06:08:39
Heap | heap.???/heap.in/heap.out/1s/65536KB
问题描述
考虑最大堆：对于最大堆每个结点的权值，均不会大于它父亲结点的权值（根结点除外）。除此之外，我们还有一个特殊的要求：对于堆中的任意一棵子树，其左子树结点中的权值应当严格小于右子树结点的权值（单亲结点和叶子结点除外）。
编写一个程序，修改最少数量树中结点的权值，使得一棵满二叉树满足上面的条件。高度为h的满二叉树恰好有2h − 1个结点
输出格式
输出一行，为最少修改的元素个数。
输入格式
输入数据第一行为二叉树的高度h(h ≤ 20)。接下来h行，第i行有2(i-1)个非负整数（不超过109），表示了整个满二叉树。注意修改的权值必须是整数但是可以是负数。
输入数据中40%的数据有h ≤ 11。
输入样例：
3
1
3 6
1 4 3 8
输出样例
4
很难诶 帮帮忙
问题描述
考虑最大堆：对于最大堆每个结点的权值，均不会大于它父亲结点的权值（根结点除外）。除此之外，我们还有一个特殊的要求：对于堆中的任意一棵子树，其左子树结点中的权值应当严格小于右子树结点的权值（单亲结点和叶子结点除外）。
编写一个程序，修改最少数量树中结点的权值，使得一棵满二叉树满足上面的条件。高度为h的满二叉树恰好有2h − 1个结点
输出格式
输出一行，为最少修改的元素个数。
输入格式
输入数据第一行为二叉树的高度h(h ≤ 20)。接下来h行，第i行有2(i-1)个非负整数（不超过109），表示了整个满二叉树。注意修改的权值必须是整数但是可以是负数。
输入数据中40%的数据有h ≤ 11。
输入样例：
3
1
3 6
1 4 3 8
输出样例
4
很难诶 帮帮忙
设i为父节点
那么如果a[i]>a[i*2] 且 a[i]>a[i*2+1] 那么 直接exit
否则 找a[i*2] 与a[i*2+1]中较大的
分两种情况。
1：
如果是a[i*2+1]较大 那么a[i]与a[i*2+1]交换 继续维护 i*2+1
2:
如果是a[i*2]较大 那么 a[i]←a[i*2] a[i*2]←a[i*2+1] a[i*2+1]←a[i]
维护 i*2与 i*2+1
谢谢~~