Sorting Algorithm(III)

这次整理的笔记主要内容是heap sort,但在说heap sort之前,先说一下树的结构和heap的结构。

  1. Tree Data Structure

    数组、链表、堆栈、队列都是线性结构,而树🌲是非线性结构的。所以如果是一些hierarchical data,就用树这种数据结构来存储,比较合适。

    一般来说,树的高度和时间开销是有关的,如果树的高度越小,常规operation的时间开销也就越小。我们来关注一下height:

    Height of the empty tree = -1

    Height of tree with one node = 0

    keep tree balance <—— make it dense and minimize its height

    1
    2
    3
    4
    5
    6
    7
        root
    / \
    ... home
    / \
    ugrad course
    / / | \
    ... cs101 cs112 cs113

    像binary tree可以分为 fully binary tree / complete binary tree / balanced binary tree / binary search tree. 简单提及一下这些不同种类的binary tree的性质。Fully Binary Tree 每一个节点都有 0 / 2 个子节点; Complete Binary Tree 每一个节点都有 2 个子节点 {the nodes are as left as possible}; Balanced Binary Tree 的高度是 $log_2 n$ ; Binary Search Tree (BST) 的 left child 的值要小于root的值,right child 的值要大于root的值。BST 的search(x) / insert(x) / remove(x)的average-case running time都是O(logn), 因为每次比较的时候search space都是对半对半的减少的~😁

下面学习一下树的构建以及遍历。常见的depth first traversal的方式有三种:in-order traversal (左子树、根节点、右子树) , pre-order traversal (根节点、左子树、右子树) ,post-order traversal (左子树、右子树、根节点)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key


# tree traversal
def Inorder(root):
if root:
Inorder(root.left)
print(root.val)
Inorder(root.right)


def Postorder(root):
if root:
Postorder(root.left)
Postorder(root.right)
print(root.val)


def Preorder(root):
if root:
print(root.val)
Preorder(root.left)
Preorder(root.right)

如果结合post-order和in-order两个arr[ ] 来构造一棵树,思路是。post[ ]的最后一个节点为root, 在in[ ]中找到root的index,root的左边都为左子树,右边都为右子树。类似下面,然后分别在左子树和右子树里面不断recursively。

1
2
3
     	 1
/ \
[4, 8, 2, 5] [6, 3, 7]
除了DFS 还有 BFS (Breadth First Traversal) / Level Order。BFS starts visiting nodes from root while DFS starts visiting nodes from leaves。下面👇这个图可以比较直观的帮助理解。如果是BFS的方式进行遍历的话,得到的就是12345

2

插一句题外话,BFS经常在graph用,看一个graph traversal pseudo code

BFS(g, s)
create a queue Q
Q.enqueue (s)
    mark s as visited
    while (Q is not empty):
        v = Q.dequeue // dequeue the top element
        for all neighbors w of v in graph G
            if w is not visited
                Q.enqueue( w )
                mark w as visited
  1. Heap

    A heap is a special tree-based data structure in which the tree is a complete binary tree.{性质上面👆有提到哈~}

    此外heap 通常被称为 Priority queue。 Queue 允许的操作是先进先出,在队尾插入元素,在队头取出元素。Heap也是在heap的末端插入元素,弹出root,但heap中元素的排列是按照一定的优先顺序进行排列的。

    heap通常可以分为两类Max-heap 和 Min-heap。这个是由heap的性质决定的,如果任一节点的值是其子树所有节点的最大值,就是max-heap。如果我们这时候extract max就是取出root,但这个时候为了保证heap的内部顺序,我们需要max-heapify。同理如果插入一个新节点的话,如果此时的父结点比自己小,就要交换新节点和父结点的位置。不断往上寻找,一直到所有节点都满足条件为止。

    首先我们来看一下binary heap的索引,root的index是1,假设node的index是p,parent[node]的index是p//2,left_child的index是2p,right_child的index是2p+1

    1
    2
    3
    4
    5
           parent
    /
    Node
    / \
    L_child R_child

    然后我们来看一下max-heapify的pseudo code

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    Max-Heapify (A,i)
    l <—— left-child index
    R <—— right-child index
    if l < heap_size[A] and A[l] > A[i]:
    greatest <-- l
    else:
    greatest <-- i
    if r < heap_size[A] and A[r] > A[greatest]:
    greatest <-- r
    if greatest != i
    swap( A[i], A[greatest] )
    Max-Heapify(A, greatest)
    end if
---------------------- 本文结束----------------------