0%

算法—优先队列and堆排序and排序应用


  • 记录学习数据结构的总结,希望可以不拘泥于细节和语言,重视应用与推演.

资料来源如下

  • 算法第四版

前言

  • 优先队列是一种抽象数据结构.支持删除最大元素及插入元素.
  • 有很多不同的实现方式,最经典的是基于二叉堆的实现.
  • 排序的逻辑:
    • 将数组输入优先队列
    • 通过优先队列 取最大元素
    • 直到取完为止,排序完成.
  • 但是请注意,优先队列的应用远远不止于此.

优先队列

  • 概念: 一种抽象数据模型,有两个必须支持的操作

    • 删除最大元素
    • 插入元素.
  • API定义

    1
    2
    3
    4
    5
    6
    7
    8
    Key delMax()//返回并 删除最大元素
    void insert(Key v)//插入元素
    void MaxPQ()//初始化优先队列
    void MaxPQ(int max)//初始化max容量优先队列
    void MaxPQ(Key[] a)//初始化 a[]的优先队列
    Key Max()//返回最大值
    boolean isEmpty()//是否为空
    int size()//优先队列大小
    • 最重要的的方法是delMax()insert()
    • 后面重要的改进都是针对这两个方法.
  • 实现方式

    • 有序数组
      • 每进来一个元素,就进行一次排序.
      • delMax() 1, insert() 看排序算法.大于线性.
    • 无需数组
      • 添加新元素不操作,删除最大元素再查找.
      • delMax() N, insert() 1.
    • 二叉堆
      • 使用二叉堆来实现优先队列.
      • 平衡了delMax()insert()
      • delMax() logN, insert() logN`.

二叉堆

    • 基于二叉堆实现的优先队列 delMax() logN, insert() logN`.
  • 这里使用数组而不是指针表示二叉树.

    • 数组中位置k的节点,父节点位置 为[k/2],子节点位置 [2k] 及 [2k+1].数组0 位置不启用.
  • 一个大小为N的完全二叉树,高度为 lgN .

  • 父节点值大于两个子节点值,当此条件全部节点满足时,称为 堆有序.

  • API 重点!

    1
    2
    3
    swim()//上浮
    sink()//下沉
    `
    • 上浮: 某个节点大于其父节点,将此节点向上浮动直到到达正确位置.
    • 下沉: 某个节点小于其子节点,将此节点向下下沉,直到到达正确位置.
    • 代码实现较容易,不再累赘.
  • 实现

    • insert() : 将元素插入数组末尾,上浮至正确位置,堆恢复有序.
    • delMax() : 删除根节点,将数组最后一个元素迁移至根节点,下沉至正确位置,堆恢复有序.
  • 与之相对的,查找删除最小元素.一切相同.

堆排序

  • 逻辑

    • 堆构造 : 将数组使用转化为二叉堆表示.
    • 下沉排序: 依次取出 最大/最小 元素,下沉恢复堆有序,直到最后一个元素为止.
    • 有趣的是,堆排序 完全不需要额外空间.
  • 堆构造

    • 上浮构造,类似优先队列的insert(). 由左向右,遍历整个数组,一个一个插入新元素,同时恢复堆有序.
      保证待插入元素左侧,一直处于堆有序,直到全部插入为止.
    • 下沉构造,类似delMax(),由右向左,不断将新元素下沉方式,保证带插入元素,右侧堆有序.
    • 上浮构造,是一个有序堆,从0 开始生长到N,下沉构造则利用了数组的每个位置已经是一个子堆根节点,只需要扫描一般的元素即可
  • 下沉构造.无需多言,递归的取根节点,不断恢复堆有序.直到排序完成.

  • 分析

    • 堆排序是目前已知的唯一可以同时最优的利用空间和时间啊的算法.
    • 但!,堆缓存的利用率太低,总是比较位置相差很远的元素.缓存未命中几率远远大于其他排序.

排序应用

  • 快速排序是目前最快的通用排序算法.

  • 库函数有实现时,才考虑自行编写.

  • 嗯,排序部分,结束…😂…