第二章数学预备知识与数据结构

数据结构

堆Heap

定义：堆Heap由一个完全二叉树的结构描述。根据父子节点键值的大小关系分为：大根堆/最大堆（父节点键值大于其任意一个子节点），小根堆/最小堆（父节点键值大于其任意一个子节点）。

zARNI1.png
有n个节点的堆T，可以用数组 $a[1···n]$ 表示，根节点存储在 $a[1]$ 。对于 $a[j]$ ，其左孩子存储在 $a[2j]$ ，右孩子存储在 $a[2j + 1]$ （如果有的话）。
堆的基本操作：上移、下移、删除、插入、构造；（以大根堆为例）

上移SIFT-UP

若某个节点 $a[i]$ 的键值大于其父节点，则违背了大根堆的特性，需要将其上移。
沿着 $a[i]$ 到根节点的唯一路径，依次比较 $a[i]$ 及其父节点的键值，将 $a[i]$ 移动到合适的位置上。

zAWAW6.md.png

SIFT-UP

输入：数组H[1···n]和位于1和n之间的索引i。

输出：上移H[i]（如果需要），以使它不大于父节点。

done <- false
if i = 1 then exit
repeat
    if key(H[i]) > key(H[i/2]) then swap(H[i], H[i/2])
    else done <- true
    i <- i / 2
until i = 1 or done

下移SIFT-DOWN

若某个节点 $a[i]$ 的键值小于其孩子节点，则违背了大根堆的特性，需要将其下移。
沿着 $a[i]$ 到子节点的路径（不唯一），依次比较 $a[i]$ 及其子节点的键值，将 $a[i]$ 移动到合适的位置上。

zAWdTs.md.png

SIFT-DOWN

输入：数组H[1···n]和位于1和n之间的索引i。

输出：上移H[i]（如果需要），以使它不小于子节点。

done <- false
if 2i > n then exit
repeat
    i <- 2i
    if i+1 <= n and key(H[i+1]) > key(H[i]) then i <- i + 1 #找到子节点中较大的那一个
    if key(H[i/2]) < key(H[i]) then swap(H[i], H[i/2])
    else done <- true
    end if
until 2i > n or done

插入INSERT

将元素x添加到数组 $a[ ]$ 的末尾，然后利用SIFT-UP调整x在 $a[]$ 中的位置。

INSERT

输入：堆H[1···n]和元素x。

输出：新的堆H[1···n+1]， x为其元素之一。

n <- n + 1
H[n] = x
SIFT-UP(H, n)

删除DELETE

将n减一，并用 $a[n]$ 替代 $a[i]$ ，然后利用SIFT调整 $a[i]$ 的位置。

DELETE

输入：非空堆H[1···n]和位于1 to n之间的索引i。

输出：删除H[i]后的新堆H[1···n-1]。

x <- H[i]; y <- H[n]
n <- n - 1
if i = n + 1 then exit #H[i]为最后一个元素直接return
H[i] <- y
if key(y) >= key (x) then SIFT-UP(H, i) #若删除的元素较大则上移
else SIFT-DOWN(H, i) #若删除元素较小则下移
end if

构造MAKEHEAP

方法一是从空堆开始，不断的调用INSERT（时间复杂度为 $O(logn)$ ），直到A中的元素全部转移，时间复杂度为 $O(nlogn)$ 。
方法二是从数组A（是一颗几乎完全的二叉树）的最后一个父节点（ $\lfloor n/2 \rfloor$ 为其索引）开始扫描至根节点，每次将以当前节点为根节点的子树转化为堆，时间复杂度为 $\Omega(n)$ 。

MAKEHEAP

输入：n个元素的数组A[1···n]。

输出：转化为堆的数组A[1···n]。

for i <- n/2 downto 1 
    SIFT-DOWN(A, i)
end for

时间复杂度分析：堆二叉树的根节点为0层，最底层为 $\lfloor logn \rfloor$ 层，第 $i$ 层有 $2^i$ 个节点（除最底层），每个节点最多交换（令 $k = \lfloor logn \rfloor$ ） $k-i$ 次，则 $T(n)$ 上界：

$T(n) \leq \sum_{i=0}^{k-1} {(k-i)}{2^i} = 2^k \sum_{i=1}^k {i/{2^i}} \leq n\sum_{i=1}^k{i/{2^i}} \leq 2n$

由于在SIFT-DOWN算法中每次循环要进行2次元素比较，且至少会执行一次循环，元素的最小比较次数为（ $T(n)$ 的下界）：

$T(n) \geq 2\lfloor n/2 \rfloor \geq n - 1$

所以MAKEHEAP时间复杂度为 $\Omega(n)$ 。

堆排序HEAPSORT

大根堆的根节点即数组中最大的键值，每次将 $A[1]$ 同 $A[j]$ 交换即全局定位其索引，堆的大小减一，然后调用SIFT-DOWN算法调整堆，逐步得到排序好的数组 $A$ 。

HEAPSORT

输入：n个元素的数组A[1···n]。

输出：以非降序排列的数组A。

MAKEHEAP(A) #将数组先构造为堆
for j <- n downto 2
    swap(A[1], A[j])
    SIFT-DOWN(A[1···j-1], 1)
end for

时间复杂度 $O(nlogn)$ ，空间复杂度 $\Omega(1)$ 。

不相交集Disjoint Sets

定义：对某个集合 $S$ ，它的一个划分（离散数学知识） $S_1，S_2，···，S_n$ 构成 $S$ 的不相交集。满足 $S_i \bigcap S_j = \emptyset, i \neq j$ 。
假定元素是整数 $1，2，···，n$ ，用数组 $A[1···n]$ 来表示， $A[j]$ 指示元素 $j$ 的父节点，空的父节点用 $0$ 指示，自然地集合x的根节点 $A[root(x)]=0$ 。

例如 $A[1···n]=\{0, 3, 0, 8, 2, 2, 1, 0, 0, 1 ,1 \}$ 被分成四个不相交集 $\{ 1, 7, 10 ,11\}, \{ 2, 3, 5, 6\}, \{4, 8\}, \{ 9\}$ 。
不相交集的基本操作：寻找元素x、将包含元素x、y的两个集合合并。

寻找元素FIND

FIND

输入：节点x。

输出：root(x)，包含x的树的根。

y <- x
while p(y) != null #寻找包含x的树的根节点
    y <- p(y) 
end while
root <- y; y <- x
while p(y) != null #路径压缩，让借助节点x指向root的节点直接指向root
    w <- p(y)
    p(y) <- root
    y <- w
end while
return root

路径压缩便于后续的合并算法，每次FIND都进行压缩可以降低树的高度。

zEeCxs.md.png

合并包含x、y的两个集合UNION

直接合并会导致树的高度太高，我们采用按秩合并措施：给每个节点存储一个非负数作为该节点的秩，记作 $rank$ （节点的秩基本上是它的高度）。在合并时，如果 $rank(x) > rank(y)$ 则 $x$ 作为父节点；在合并时，如果 $rank(y) > rank(x)$ 则 $y$ 作为父节点；如果二者相等则让任意一个节点（这里我们以 $y$ 为例）作为父节点并 $rank + 1$ 。

UNION

输入：两个元素x和y。

输出：包含x和y的两个树的合并，原来的树被破坏。

u <- FIND(x); v <- FIND(y)
if rank(x) <= rank(v) then
    p(u) <- v
    if rank(u) = rank(v) then rank(v) <- rank(v) + 1
else p(v) <- u
end if

2算法设计与分析笔记(Authored by M.H Alsuwaiyel, Saudi)

2算法设计与分析笔记(Authored by M.H Alsuwaiyel, Saudi)

第二章数学预备知识与数据结构

数据结构

堆Heap

上移SIFT-UP

下移SIFT-DOWN

插入INSERT

删除DELETE

构造MAKEHEAP

堆排序HEAPSORT

不相交集Disjoint Sets

寻找元素FIND

合并包含x、y的两个集合UNION

友情链接更多精彩内容

2算法设计与分析笔记(Authored by M.H Alsuwaiyel, Saudi)

第二章 数学预备知识与数据结构

数据结构

堆Heap

上移SIFT-UP

下移SIFT-DOWN

插入INSERT

删除DELETE

构造MAKEHEAP

堆排序HEAPSORT

不相交集Disjoint Sets

寻找元素FIND

合并包含x、y的两个集合UNION

友情链接更多精彩内容

第二章数学预备知识与数据结构