左偏树的性质
- 本节点的键值key小于其左右子节点键值key(与二叉堆相同);
- 本节点的左子节点的距离大于等于本节点的右子节点(这意味着每个节点中除了要存储键值外, 还需要一个额外的dist存储距离);
- 节点的距离是其右子节点的距离+1(这意味着, 一个节点的dist是从它出发到达最近终端节点的距离);
斜堆的性质
- 本节点的键值key小于其左右子节点键值key;
- 斜堆节点不存储距离dist值, 取而代之的是在每次合并操作时都做swap处理(节省了存储空间);
Update your browser to view this website correctly. Update my browser now