6. 堆的实现

阅读信息

约 199 个字  2 分钟  本页总访问量：加载中... 次

Class Five

优先队列(堆)

目标功能

insert 和 delete,且每次 delete 删除最大值或最小值

实现(小根堆为例)

• 几种传统方法:数组,链表,有序数组,有序链表...
• 小根堆:每个节点都是它所在子树的最小节点(order property).
• 从根节点到叶节点的任何路径都是从小到大.每次插入新节点时,在当前节点调成从小到大即可.(类似插入排序,由 i 跟 i-1 比换成 i 跟 i/2 比)
• 一层一层插入,得到完全二叉树(structure property).
• 多叉堆?树的高度降低,但总时间不变.
• 插入:

// 插入元素
bool Insert(Heap H, int x){
  if (堆已满) return false

  i表示当前堆的大小(原先大小+1)
  for (i的父亲比i处的值大,i/2) {
    i的父亲下移到i处
  }
  // 此时i的父亲比i小,i表示要插入的位置
  第i位的值赋为x
}

// 删除(小根堆)
int DeleteMin(Heap H) {
  if (堆是空的)
    return ERROR

  min表示最小值(根)
  x表示当前堆的最后一个元素(堆的大小为原先大小-1)
  pa表示遍历的节点,child表示较小的子节点

  for (pa从根开始,pa的儿子不超过堆的大小,pa更新为child) {
    假设较小的child是pa的左儿子
    if (child不是最后一个,而且右儿子的值更小) {
      child更新为pa的右儿子
    }

    if (child的值比最后一个元素大)
      break
    else
      pa的值下移到child
  }

  // 此时pa表示x要插入的位置
  将第pa位赋为x

  return min
}

动态等价关系

给定元素和几个元素之间的等价关系,求任意两个元素之间是否等价.

// 构建
while (读入a和b等价) {
  if (a的集合!=b的集合) {
    合并两个集合
  }
}

// 查询
读入两个要查询的元素
if (a的集合==b的集合) {
  print (true)
}

用数组表示:下标代表元素,值代表根