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

发表于 2018-06-02 分类于数据结构阅读次数： Disqus：本文字数： 1.4k 阅读时长 ≈ 1 分钟

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

资料来源如下

算法第四版

前言

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

优先队列

概念: 一种抽象数据模型,有两个必须支持的操作
- 删除最大元素
- 插入元素.

API定义

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 重点!
```
swim()//上浮
sink()//下沉
```
- 上浮: 某个节点大于其父节点,将此节点向上浮动直到到达正确位置.
- 下沉: 某个节点小于其子节点,将此节点向下下沉,直到到达正确位置.
- 代码实现较容易,不再累赘.
实现
- insert() : 将元素插入数组末尾,上浮至正确位置,堆恢复有序.
- delMax() : 删除根节点,将数组最后一个元素迁移至根节点,下沉至正确位置,堆恢复有序.
与之相对的,查找删除最小元素.一切相同.

堆排序

逻辑
- 堆构造 : 将数组使用转化为二叉堆表示.
- 下沉排序: 依次取出最大/最小元素,下沉恢复堆有序,直到最后一个元素为止.
- 有趣的是,堆排序完全不需要额外空间.
堆构造
- 上浮构造,类似优先队列的insert(). 由左向右,遍历整个数组,一个一个插入新元素,同时恢复堆有序.
  保证待插入元素左侧,一直处于堆有序,直到全部插入为止.
- 下沉构造,类似delMax(),由右向左,不断将新元素下沉方式,保证带插入元素,右侧堆有序.
- 上浮构造,是一个有序堆,从0 开始生长到N,下沉构造则利用了数组的每个位置已经是一个子堆根节点,只需要扫描一般的元素即可
下沉构造.无需多言,递归的取根节点,不断恢复堆有序.直到排序完成.
分析
- 堆排序是目前已知的唯一可以同时最优的利用空间和时间啊的算法.
- 但!,堆缓存的利用率太低,总是比较位置相差很远的元素.缓存未命中几率远远大于其他排序.

排序应用

快速排序是目前最快的通用排序算法.
库函数有实现时,才考虑自行编写.
嗯,排序部分,结束…😂…

disqus
utterances