堆(heap)
2025-07-22
4
堆的性质堆中某个结点的值总是不大于(或不小于)其节结点的值;堆通常是一棵完全二叉树。需要用到知识点:完全二叉树用数组来存储,它的下标和位置关系第一种:数组从0开始存储如果i是父节点左子树位置:2i+1右子树位置:2i+2求父节点:floor((i-1)/2)第二种:数组从1开始存储如果i是父节点左子树位置:2i右子树位置:2i+1

堆的性质

堆中某个结点的值总是不大于(或不小于)其节结点的值;

堆通常是一棵完全二叉树。

需要用到知识点:

完全二叉树用数组来存储,它的下标和位置关系
第一种:数组从0开始存储
如果i是父节点
左子树位置:2i+1
右子树位置:2i+2
求父节点:floor((i-1)/2)
第二种:数组从1开始存储
如果i是父节点
左子树位置:2i
右子树位置:2i+1
求父节点:floor(i/2)