数据结构与算法之总复习（深度优先搜索、堆、动态规划在图论中的运用

参考资料：《算法导论》第三版

深度优先搜索

一个图中所有不在深度优先搜索树中的边，都是后向边

在对无向图的深度优先搜索中，从来不会出现前向边和横向边

MAX-HEAPIFY时间复杂度：O(lgn)

BUILD-MAX-HEAP时间复杂度：线性时间复杂度。功能：从无需的输入数组中构造一个最大堆。（堆）

HEAPSORT：时间复杂度为O(nlgn)。功能是对一个数组进行原址排序。（数组本身）

一个栗子。

Show how heapsort processes the input 142, 543, 123, 65, 453, 879, 572, 434,

111, 242, 811, 102.

第一步：先把这些数据放进一个列表里。[142, 543, 123, 65, 453, 879, 572, 434,

111, 242, 811, 102]。然后构建一个堆的图形。

第二步：调用BUILD-MAX-HEAPIFY。从最后一个parent开始，一直到parent。

第三步：调用HEAPSORT。具体就是把堆的root元素和最后一个元素交换，并把这个root元素放进列表的最后一个位置，列表容量减一，然后对新的root元素调用MAX-HEAPIFY。

以以上这道邀请参加聚会的题目为例。