Question

什么叫堆？小根堆的定义是什么？大根堆的定义又是什么？

Answer 1

堆是一种经过排序的完全二叉树，其中任一非终端节点的数据值均不大于（或不小于）其左子节点和右子节点的值。

最大堆和最小堆是二叉堆的两种形式。

最大堆（大根堆）：根结点的键值是所有堆结点键值中最大者。

最小堆（小根堆）：根结点的键值是所有堆结点键值中最小者。

而最大-最小堆集结了最大堆和最小堆的优点，这也是其名字的由来。

最大-最小堆是最大层和最小层交替出现的二叉树，即最大层结点的儿子属于最小层，最小层结点的儿子属于最大层。

以最大（小）层结点为根结点的子树保有最大（小）堆性质：根结点的键值为该子树结点键值中最大（小）项。

扩展资料

在考虑将以Ki为根的子树排成堆时，以Ki+1，Ki+2，…，Kn-1为根的子树已经是堆，所以这时如果有Ki≤K2i+1和Ki≤K2i+2，则不必改变任何结点的位置，以Ki为根的子树就已经是堆；否则就要适当调整子树中结点的位置以满足堆的定义。由于Ki的左、右子树都已经是堆，根结点是堆中最小的结点，所以调整后Ki的值必定是原来K2i+1和K2i+2中较小的一个。

不妨假定K2+1较小，将Ki与K2i+1交换位置，这样调整后Ki≤K2i，Ki≤K2i+1，并且以K2i+2为根的子树原来已经是堆，不必再作任何调整，只有以K2i+1为根的子树由于K2i+1的值已经发生变化（与Ki交换了），所以有可能不满足堆的定义（当K2i+1的左、右子树已经是堆）。

这时可重复上述过程，考虑将K2i+1以为根的子树排成堆。如此一层一层递推下去，最多可以一直进行到树叶。由于每步都保证将子树中最小的结点交换到子树的根部，所以这个过程是不会反馈的。它就像过筛一样，把最小的关键码一层一层选择出来。

参考资料来源：百度百科-最小堆

Answer 2

堆是一种经过排序的完全二叉树，其中任一非终端节点的数据值均不大于（或不小于）其左孩子和右孩子节点的值。
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆。