2020-03-06-algorithm-2

发表于 | 分类于
字数统计: 183字 | 阅读时长 ≈ 1分钟

堆

定义：堆是一个完全的二叉树，每个节点都满足（任一父节点的键值都不小于子节点的键值）

image-20200306143043099

非升序排列的二叉树

image-20200306143353432

存储的方式

  • 根节点存在H[1]
  • 节点H[i]左右子节点存在H[2i]、H[2i+1]
  • 节点H[j]父节点为

image-20200306143720731

基本操作

  • make-heap nlog(n) 即

    insert

    shift-down

    image-20200306151812583

    image-20200306152913995

  • insert(H,x) 插入所需时间为O(logn)树的高度

  • delete(H,i)

    image-20200306145933371

  • delete-max(H)

image-20200306143909302

辅助运算

  • Shift-up
  • Shift-down

image-20200306144102573

image-20200306144632289

image-20200306145341282

image-20200306145535439

堆排序

image-20200306153013519

  • 创建最大堆
  • 把根节点与最后一个节点交换
  • 再创建最大堆
  • 再交换

不相交集(Disjoint Sets)

  • 每个元素不相同
  • 可以用树表示

image-20200306155841259

image-20200306160011900

image-20200306160421170

image-20200306161050838

路径压缩师，秩不会变

image-20200306162018074