您现在的位置:首页 > >

数据结构与算法(Python语言描述)课件DS_053_优先级队列和堆排序

发布时间:

2016 Fall 《数据结构》

优先级队列、堆排序

2017/1/9

中国海洋大学数学科学学院

1

优先级队列 Priority Queue

2017/1/9

优先级队列
?

与栈和队列一样:
?

可以保存数据元素,访问、入、出

?

不同之处:每个数据都附有优先级,任何时候访 问、出对列的总是当前队列中最优先的元素
?

“有序” 队列!

2017/1/9

优先级(Priority)
?

代表了数据的某种性质:
?

各项工作的计划开始时间 一个大项目中各种工作任务的急迫程度 银行客户的诚信评估,用于决定优先贷款等

?

?

2017/1/9

实现方式1:sorted list
class PrioQue: def __init__(self, elist = []): self.elems = list(elist) self.elems.sort(reverse = True) # 由大到小排序 def is_empty(self): return self.elems == [] def peek(self): if self.is_empty(): raise PrioQueueError("in top") return self.elems[-1]

2017/1/9

def dequeue(self): if self.is_empty(): raise PrioQueueError("in pop") return self.elems.pop() # 元素由大到小排,直接pop def enqueue(self, e): i = len(self.elems) - 1 while i >= 0: if self.elems[i] <= e: i -= 1 else: break self.elems.insert(i+1, e) # 循环结束时,遇到了第一个大于e的元素elems[i] # 入队列的时间复杂度: O(n)
2017/1/9

线性方式两种策略
?

入队列时保持有序,出队列直接pop;
?

入队列:O(n) 出对列:O(1)

?

?

入队列时不处理,出队列时搜索最优先:
?

入队列:O(1) 出队列:O(n)

?

2017/1/9

堆结构 Heap

2017/1/9

大顶堆 和 小顶堆

“土堆”
?

堆顶的“优先级”最高
?

【数最小 ~~ 小顶堆】

上面轻,下面沉; 上面气泡,下面石头 气泡上浮,石头下沉

?

2017/1/9


?

是一棵“基本有序”的完全二叉树 !
?

任何结点的值都小于等于其左右孩子的值!

堆(递归定义)
?

空树; 若非空,是一棵完全二叉树,满足:
? 若根结点有左孩子,则根结点值小于等于其左孩子值; ? 若根结点有右孩子,则根结点值小于等于其右孩子值; ? 左右子树仍然是堆!

?


?

特点:
?

最优先的元素位于堆顶;

?

左右子树仍然是堆;
由根到叶子的路径上,结点是有序的;

?

?

应用:
?

表示优先级队列!

?

堆排序

2017/1/9

堆的表示

2017/1/9

回忆:完全二叉树的性质
?

适合顺序存储
?

结点i 的孩子: 2 * i + 1, 2 * i + 2 结点i 的双亲: ?( i -1 )/2?

?

?

由根到叶子的路径长 ~ logn
?

含有n个结点的完全二叉树的深度: ? log2n ?

2017/1/9

堆的表示
?

顺序存储!!!

0 12

1 36

2 24

3 85

4 47

5 30

6 53

7 91

堆的另一种定义
?

含n个元素的线性序列elem[0,…n-1],满足:
?

elem[i] <= elem[2 * i + 1], 如果2*i+1 <n elem[i] <= elem[2 * i + 2], 如果2*i+2<n

?

0

1

2

3

4

5

6

7

12

36

24

85

47

30

53

91

2017/1/9

对堆结构的理解
? ?

存储上:线性结构 逻辑上:完全二叉树(层次结构)

2017/1/9

堆的维护——插入删除

2017/1/9

如何向堆中插入元素???

0 12

1 36

2 24

3 85

4 47

5 30

6 53

7 91

25

2017/1/9

尾部插入元素后的siftup
12 36 24

85
91 12 36 25 91 85 47 30 25

47

30

53

12

24
53 36 91

25 47 85 30

24 53

siftup——从尾部开始沿双亲上行

j = (j-1)/2 j = (last-1)/2 i=j i = last

2017/1/9

siftup——向上筛选
def siftup(self, e, last): elems = self.elems i, j = last, (last-1)//2 # i上行范围[last, 0) # j是i的双亲

while i > 0 and e < elems[j]: elems[i] = elems[j] # 把双亲挤下来——对应小数上浮 i, j = j, (j-1)//2 # 继续上行 elems[i] = e

时间复杂度:O(logn)

2017/1/9

如何由堆中删除元素???

0

1

2

3

4

5

6

7

13

38

27

49

76

65

49

97

2017/1/9

输出堆顶后的siftdown过程
13 38 49 97 97 38 49 76 65 27 49 49 38 76 65 27 97 49 49 76 65

27
49 97 49

38 76 65

27 49

27

38
76

49

65

97

输出堆顶后的siftdown过程

左右两棵子树已经是堆, 将最后一个元素充填堆顶, 让其根据“重量”自然下沉: 效果是把小的孩子向上挤!

siftdown——从根开始沿小孩子下行
i

i 的小孩子 j

i
j 是i的小孩子

2017/1/9

siftdown——向下筛选
def siftdown(self, e, begin, end): elems = self.elems, i, j = begin, begin*2+1 # j的下行范围 < end

while j < end: if j+1 < end and elems[j+1] < elems[j]: j += 1 # 选出小孩子

if e < elems[j]: break
elems[i] = elems[j] # 孩子挤上去——对应大数下沉 i, j = j, 2*j+1 # 继续下行 elems[i] = e 时间复杂度:O(logn)
2017/1/9

建堆

2017/1/9

如何建堆???
0 1 2 3 4 5 6 7

49

38

65

97

76

13

27

49

49

38 97 76

65 13

27

49
2017/1/9

如何建堆???
?

明确:
?

最先一个没有孩子的结点的编号为:
? ?( n -1 -1 )/2? +1 = n/2

?

从 n/2 开始的每个结点没有孩子,各自成一个堆
49 38 97 49 76 13 65 27

n=8 index(76) = 4

2017/1/9

建堆过程
?

起始:对于最后一个有孩子的结点,它的左右子树都 已经是堆;

?

自后向前,逐结点进行siftdown操作,将子堆不 断合成更大些的堆,最终形成一个大堆。

2017/1/9

从最后一个 有孩子的结点 开始,逐个 siftdown

建堆过程

建堆
def buildheap(self): end = len(self.elems) for i in range(end//2-1, -1, -1): self.siftdown(self.elems[i], i, end) # siftdown 操作范围:[i, end)

2017/1/9

建堆的时间复杂度
?

建堆时,从倒数第二层的加点开始,自后向前, 逐步进行siftdown;

?

siftdown过程中,每一步做两次比较;
?

两个孩子选出最小的 sift的结点和小的孩子结点比较

?

2017/1/9

建堆的时间复杂度
? ? ?

第i层向下sift的层数最多为 h - i 第i层最多 2i 个结点 总的比较次数为:

?

时间复杂度: O(n)

2017/1/9

优先级队列的堆实现

2017/1/9

实现方式2:堆
class PrioQueue: def __init__(self, elist = []): self.elems = list(elist) if elist != []: self.buildheap() def is_empty(self): return len(self.elems) == 0 def peek(self): if self.is_empty(): raise PrioQueueError("in top") return self.elems[0]

2017/1/9

def enqueue(self, e): self.elems.append(None) # 添加占位 self.siftup(e, len(self.elems)-1) #last def dequeue(self): if self.is_empty(): raise PrioQueueError("in pop") elems = self.elems e0 = elems[0] e = elems.pop() # 弹出最后一个,“占位”elem[0] if len(elems) > 0: self.siftdown(e, 0, len(elems)) #[0,len) return e0

2017/1/9

堆方式
? ? ?

初始一次性建堆: O(n) 出队列:O(logn) 入队列:O(logn)

2017/1/9

堆排序 HeapSort

2017/1/9

堆结构的应用——堆排序
? ?

step1:对序列建堆; step2: 不断输出堆顶元素,然后通过siftdown再 次调整成元素数少1的堆,直到所有元素输出。

2017/1/9

堆排序

小顶堆排序的结果是由大到小!
2017/1/9

堆排序
def heap_sort(elems): def siftdown(elems, e, begin, end): # [begin, end) i, j = begin, begin*2+1 while j < end: if j+1 < end and elems[j+1] < elems[j]: j += 1 if e < elems[j]: break elems[i] = elems[j] i, j = j, 2*j+1 elems[i] = e end = len(elems) for i in range(end//2-1, -1, -1): siftdown(elems, elems[i], i, end) for i in range((end-1), 0, -1): e = elems[i] elems[i] = elems[0] siftdown(elems, e, 0, i)

# 初始建堆

# 不断输出堆顶,然后调整 # 堆顶输出后,放到当前的最后 # 注意:堆的范围在缩小

堆排序的复杂度分析
?

时间:O(n logn)
? ?

建堆:O(n) 不断输出堆顶、调整: O(n logn)
共n个元素 ? 每个元素输出后的siftdown,不超过树的深度 ? log(n-1) + … + log(2) < n logn
?

?

空间:O(1)

2017/1/9

小结

2017/1/9

要求掌握!
?

堆结构的特点
?

逻辑上是“基本有序”的完全二叉树,小顶堆堆顶最小!

?

堆调整
? ?

Siftup——小数上浮,将大的双亲挤下来; Siftdown——大数下沉,将小孩子挤上去;

?

建堆
? ?

过程:自后向前不断siftdown,逐步合成一个大堆 O(n)

?

堆排序
? ?

方法:不断输出堆顶,回填后再siftdown O(nlogn)

2017/1/9



热文推荐
猜你喜欢
友情链接: 医学资料大全 农林牧渔 幼儿教育心得 小学教育 中学 高中 职业教育 成人教育 大学资料 求职职场 职场文档 总结汇报