左偏树和斜堆

左偏树的性质

  • 本节点的键值key小于其左右子节点键值key(与二叉堆相同);
  • 本节点的左子节点的距离大于等于本节点的右子节点(这意味着每个节点中除了要存储键值外, 还需要一个额外的dist存储距离);
  • 节点的距离是其右子节点的距离+1(这意味着, 一个节点的dist是从它出发到达最近终端节点的距离);

斜堆的性质

  • 本节点的键值key小于其左右子节点键值key;
  • 斜堆节点不存储距离dist值, 取而代之的是在每次合并操作时都做swap处理(节省了存储空间);
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×