当前课程知识点：Data Structures and Algorithm Design Part II >  10.Priority Queue >  C.Heapsort >  10C-4

返回《Data Structures and Algorithm Design Part II》慕课在线视频课程列表

10C-4在线视频

下一节:10XA-1

返回《Data Structures and Algorithm Design Part II》慕课在线视频列表

10C-4课程教案、知识点、字幕

我们来看堆排序算法的一个具体实例，考察这样一个规模为5的向量，

我们首先从逻辑上将它视作为一棵完全二叉树，

其中有两个内部节点，也就是2和4，

于是我们采用Floyd算法分别对2和4分别做一趟下滤，即可最终得到这样一个完全二叉堆。

至此，也就完成了算法的预处理步骤，

接下来我们进入算法的主体循环，

请注意在一开始整个向量都是未排序的部分，

而已排序的部分初始为空。

即便如此，我们依然可以使用算法的基本策略，

也就是令当前的堆顶与末元素互换位置，

互换之后的瞬间应该是这样，原来的末元素2成为了堆顶，

而5则在逻辑上从原来的堆中分离出来，加入原本为空的S。

也就是说，已排序的序列此时已经拥有了第一个元素。

当然，我们还需要对新的堆顶做下滤调整，

从而使得剩下的4个元素依然恢复为一个堆，尽管规模减少了一个单位。

不出意外，接下来的最大元4也成为了新的堆顶，

因此在下一轮迭代中，我们依然将这个新的堆顶与当前的末元素互换位置，

在逻辑上这等效于将堆顶摘出，并归入到有序序列中。

同样我们仍需对新的根节点做一次下滤调整，

从而使得剩余三个元素能够继续保持为一个合法的大顶堆。

不出预料，当前尚未排序的元素中的最大者3也必然就是堆顶。

因此，我们也只需令它与当前的末元素2做一次对换，

在逻辑上这依然等同于将这个堆顶摘出并归入到有序序列中。

此后再经过一轮下滤调整，剩余元素也依然会恢复为一个合法的大顶堆，

尽管此时已经只剩最后的两个元素。

为了节省时间，我们把这部分内容留给你在课后独立完成。

Data Structures and Algorithm Design Part II课程列表：

07.Binary Search Tree

-A.introduction

--07A-1

--07A-2

--07A-3

--07A-4

--07A-5

-A.introduction--Homework

-B1.BST : search

--07B1-1

--07B1-2 查找：算法

--07B1-3 查找：理解

--07B1-4 查找：实现

--07B1-5 查找：语义

-B1.BST : search--Homework

-B2.BST : insertion

--07B2-1

--07B2-2

-B2.BST : insertion--Homework

-B3.BST : removal

--07B3-1

--07B3-2

--07B3-3

--07B3-4

-B3.BST : reomval--Homework

-C.balance+equivalence

--07C-1

--07C-2

--07C-3

--07C-4

--07C-5

-C.balance+equivalence--Homework

-D1.AVL : rebalance

--07D1-1

--07D1-2

--07D1-3

--07D1-4

--07D1-5

-D1.AVL : rebalance--Homework

-D2.AVL : insertion

--07D2-1

--07D2-2

--07D2-3

-D2.AVL : insertion--Homework

-D3.AVL : removal

--07D3-1

--07D3-2 删除：双旋

--07D3-3 删除：实现

-D3.AVL : removal--Homework

-D4.AVL : (3+4)-construction

--07D4-1

--07D4-2

--07D4-3

--07D4-4

-D4.AVL : (3+4)-construction--Homework

-Homework

--Homework

08.ABST I

-A1.Splay_Tree.splay1

--08A1-1

--08A1-2

--08A1-3

--08A1-4

--08A1-5

--08A1-6

--08A1-7

--Homework

-A2.Splay_Tree.splay2

--08A2-1

--08A2-2

--08A2-3

--08A2-4

--08A2-5

--08A2-6

--08A2-7

--Homework

-A3.Splay_Tree.implementation

--08A3-1

--08A3-2

--08A3-3

--08A3-4

--08A3-5

--08A3-6

--08A3-7

--Homework

-B1.B-Tree.motivation

--08B1-1

--08B1-2

--08B1-3

--08B1-4

--08B1-5

--08B1-6

--Homework

-B2.B-Tree.structure

--08B2-1

--08B2-2

--08B2-3

--08B2-4

--08B2-5

--08b2-6

--08B2-7

--08B2-8

--Homework

-B3.B-Tree.search

--08B3-1

--08B3-2

--08B3-3

--08B3-4

--08B3-5

--08B3-6

--Homework

08.ABST II

-B4.B-Tree.insertion

--08B4-1

--08B4-2

--08B4-3

--08B4-4

--08B4-5

--Homework

-B5.B-Tree.removal

--08B5-1

--08B5-2

--08B5-3

--08B5-4

--08B5-5

--Homework

-XA1.Red-Black.motivation

--08XA1-1

--08XA1-2

--08XA1-3

--08XA1-4

--Homework

-XA2.Red-Black.structure

--08XA2-1

--08XA2-2

--08XA2-3

--08XA2-4

--08XA2-5

--08XA2-6

--08XA2-7

--Homework

-XA3.Red-Black.insertion

--08XA3-1

--08XA3-2

--08XA3-3

--08XA3-4

--08XA3-5

--08XA3-6

--Homework

-XA4.Red-Black.removal

--08XA4-1

--08XA4-2

--08XA4-3

--08XA4-4

--08XA4-5

--08XA4-6

--08XA4-7

--08XA4-8

--08XA4-9

-Homework

--Homework

09.Dictionary

-B.hashing.principle

--09B-1

--09B-2

--09B-3

--09B-4

--09B-5

--09B-6

--Homework

-C.Hashing.Hash-Function

--09C-1

--09C-2

--09C-3

--09C-4

--09C-5

--09C-6

--09C-7

--09C-8

--09C-9

--09C-A

--09C-B

--Homework

-D1.Hashing.Solving-Collision-1

--09D1-1

--09D1-2

--09D1-3

--09D1-4

--09D1-5

--Homework

-D2.Hashing.Solving-Collision-2

--09D2-1

--09D2-2

--09D2-3

--09D2-4

--09D2-5

--09D2-6

--09D2-7

--09D2-8

--Homework

-E.Bucketsort

--09E-1

--09E-2

--09E-3

--Homework

-Homework

--Homework

10.Priority Queue

-A1.motivation

--10A1-1

--10A1-2

--10A1-3

--Homework

-A2.Basic_Implementations

--10A2-1

--10A2-2

--10A2-3

--Homework

-B1.Complete_Binary_Heap.structure

--10B1-1

--10B1-2

--10B1-3

--10B1-4

--Homework

-B2.Complete_Binary_Heap.insertion

--10B2-1

--10B2-2

--10B2-3

--10B2-4

--Homework

-B3.Complete_Binary_Heap.removal

--10B3-1

--10B3-2

--10B3-3

--10B3-4

--Homework

-B4.Complete_Binary_Heap.heapification

--10B4-1

--10B4-2

--10B4-3

--10B4-4

--10B4-5

--Homework

-C.Heapsort

--10C-1

--10C-2

--10C-3

--10C-4

--Homework

-XA1.Leftist_Heap.structure

--10XA-1

--10XA1-2

--10XA1-3

--10XA1-4

--10XA1-5

--10XA1-6

--Homework

-XA2.Leftist_Heap.merge

--10XA2-1

--10XA2-2

--10XA2-3

--10XA2-4

--Homework

-XA3.Leftist_Heap.insertion+removal

--10XA3-1

--10XA3-2

-Homework

--Homework

11.String I

-A.ADT

--11A-1

--11A-2

--11A-3

--Homework

-B1.Pm

--11B1-1

--11B1-2

--Homework

-B2.brute-force

--11B2-1

--11B2-2

--11B2-3

--11B2-4

--Homework

-C1.Kmp.memorization

--11C1-1

--11C1-2

--11C1-3

--11C1-4

--Homework

-C2.Kmp.lookup-table

--11C2-1

--11C2-2

--11C2-3

--Homework

-C3.Kmp.understanding_next[]

--11C3-1

--11C3-2

--11C3-3

--Homework

-C4.Kmp.constructing_next[]

--11C4-1

--11C4-2

--11C4-3

--Homework

-C5.Kmp.amortization

--11C5-1

--11C5-2

--Homework

-C6.Kmp.improvement

--11C6-1

--11C6-2

--11C6-3

--11C6-4

--11C6-5

11.String II

-D1.BM_BC.begin_with_the_end

--11D1-1

--11D1-2

--11D1-3

--11D1-4

-D2.BM_BC.bad_character

--11D2-1

--11D2-2

-D3.BM_BC.constructing_bc[]

--11D3

-D4.Bm_BC.performance

--11D4-1

--11D4-2

-E1.Bm_GS.good-suffix

--11E1-1

--11E1-2

--11E1-3

-E2.Bm_GS.constructing_gs[]

--11E2

-E3.Bm_GS.performance

--11E3-1

--11E3-2

-F1.KR.fingerprint

--11F1-1

--11F1-2

--11F1-3

-F2.KR.hashing

--11F2-1

--11F2-2

--11F2-3

--11F2-4

-Homework

--Homework

12.Sorting

-A1.Quicksort.algorithm

--12A1-1

--12A1-2

--12A1-3

--12A1-4

-- 12A1-5

--Homework

-A2.Quicksort.performance

--12A2-1

--12A2-2

--12A2-3

--Homework

-A4.Quicksort.Variation

--12A4-1

--12A4-2

--12A4-3

--12A4-4

--12A4-5

-B1.Selection.mode

--12B1-1

--12B1-2

--12B1-3

--12B1-4

--12B1-5

-B2.Selection.Median

--12B3-1

--12B3-2

--12B3-3

--12B3-4

--12B3-5

--12B3-6

--Homework

-C1.Shellsort.Shell's sequence

--12C1-1

--12C1-2

--12C1-3

--12C1-4

--12C1-5

--Homework

-C2.Shellsort.Inversion

--12C2-1

--12C2-2

--12C2-3

-Homework

--Homework

10C-4笔记与讨论

也许你还感兴趣的课程:


  1. 汽车销售实务(2021秋)

  2. 电路分析基础(2021秋)

  3. 工程结构抗震设计(2021暑假班)

  4. 云计算(2021秋)

  5. 超声检查技术(2021秋)

  6. 弟子规与人生修炼(2021秋)

  7. 现代教育技术(2021秋)

  8. 创意思维表现(2021秋)

  9. 环境监测(2021秋)

  10. 教育心理学(2021秋)

  11. Data Structures and Algorithm Design Part II(Self-Paced)

  12. Pharmacology(Round 1)

  13. Diagnostics(Round 1)

  14. Medical Nursing(Round 1)

  15. The Experiment for Mechanical Manufacturing Process Design and Simulation(Round 1)

  16. Chinese Language --Express to HSK(Round 1)

  17. World Arena: Facing Globalization(Self-Paced)

  18. Skills in English for General Academic Purposes(Round 1)

  19. Plato, Socrates, and the Birth of Western Philosophy(Self-Paced)

  20. Combinatorics and Algorithms Design(Self-Paced)
© 柠檬大学-慕课导航 课程版权归原始院校所有，
本网站仅通过互联网进行慕课课程索引，不提供在线课程学习和视频，请同学们点击报名到课程提供网站进行学习。