数据结构键值是什么而且下面这个怎么理解?根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆,又称最小堆.根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者,称为大根堆,又称最大堆.举几个例子. 数学
网友回答
【答案】 这里指的数据结构是指堆的结点吧.
堆其实就是一种树结构,对小根堆而言,任何一个结点的值都比它所有子树的所有结点的值都小,这里用于两个结点间作比较的值就是结点的键值.其实只要它的键值比它的子节点的键值小就行了,每个节点都比它的子节点的键值小,那么根节点的键值肯定比它所有的子孙结点的键值都小.
1
2 4
4 3 9 8
就如这个数图所表示（上面的数字是它下方两个数字的根节点）,每个有子节点的节点键值都比它的子节点的键值小（1比它的子节点2、4小,左子树2比它的子节点4、3都小,右子树4比它的子结点9、8都小）,这样就使得每个节点都是以它为根的子树中键值小最的节点,这样的子树本身就是一个小根堆,整棵树的根结点也是这棵树里最小的,所以它也是一个小根堆.这应该能理解了吧!大根堆的比法与小根堆相同,只是根的值比子节点的大.同样上面的数字,也给一个大根堆.
9
8 4
4 2 3 1