堆(heap),是⼀棵有着特殊性质的完全⼆叉树,可以⽤来实现优先级队列(priority queue),
堆需要满⾜以下性质:
堆需要满⾜以下性质:
- 是⼀棵完全⼆叉树;
- 对于树中每个结点,如果存在⼦树,那么该结点的权值⼤于等于(或⼩于等于)⼦树中所有结点的权值。
如果根结点⼤于等于⼦树结点的权值,称为⼤根堆;反之,称为⼩根堆( 比如99这个结点,有左右子树,且99这个值大于左子树所有节点的值,也大于右子树所有节点的值)
练习:判断下图中的二叉树是否是堆。如果是堆,判断是大根堆还是小根堆
(1)可大可小(2)大根堆(3)不是堆(40比34大)(4)小根堆(5)不是堆(不是完全二叉树)(6)不是堆(28比29小)