1 / 50
文档名称:

数据结构与算法分析第六章 优先队列(堆)课件.ppt

格式:ppt   大小:1,341KB   页数:50页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

数据结构与算法分析第六章 优先队列(堆)课件.ppt

上传人:012luyin 2022/9/26 文件大小:1.31 MB

下载得到文件列表

数据结构与算法分析第六章 优先队列(堆)课件.ppt

相关文档

文档介绍

文档介绍:该【数据结构与算法分析第六章 优先队列(堆)课件 】是由【012luyin】上传分享,文档一共【50】页,该文档可以免费在线阅读,需要了解更多关于【数据结构与算法分析第六章 优先队列(堆)课件 】的内容,可以使用淘豆网的站内搜索功能,选择自己适合的文档,以下文字是截取该文章内的部分文字,如需要获得完整电子版,请下载此文档到您的设备,方便您编辑和打印。第六章优先队列(堆)
1
本章纲要



-堆



2

队列
FIFO
排队等候买票
优先级
例如,救护车过红灯
对队列而言,队首元素先出队,暗含了队首优先级最高。
3

优先队列
队列中元素具有不同的优先级,优先级高的元素先出队(deque)
遵守队列队首先出队的规则
因此,在优先队列中,优先级最高的元素应在队首。
入队(enque)插入(insert)
出队(deque)(deletemin)
4

实现
链表
数组
二叉查找树
5

高为h的完全二叉树有2h到2h+1-1个节点,完全二叉树的高为O(logN)
完全二叉树的数组存储
09
17
65
23
45
78
87
53
31
1
2
3
4
5
6
7
8
9
堆顶元素值最小
09
17
65
23
45
78
87
53
31
123456789
最小堆
0
7

ADT
假设关键字越小,优先级越高
初始化
8

Deletemin
即删除堆顶元素,数组中1号位置元素
删除操作破坏了完全二叉树结构
下滤
见图6-9到6-11。
10

DecreaseKey
减少关键字的值提高优先级
上滤
任务管理器中的进程管理
DecreaseKey
增大关键字的值降低优先级
下滤
Delete
首先decreasekey,然后deletemin
进程被终止
11

Buildheap(构建堆)

依次插入每个元素,总保证堆序性

N个元素不考虑堆序性,直接存储到一个完全二叉树中;
从第N/2个元素到第一个元素依次使用下滤,就得到一个堆。
12