数据结构备忘录

1. 链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。 每个结点包括两个部分：

  • 一个是存储数据元素的数据域
  • 另一个是存储下一个结点地址的指针域

2. 查找

线性查找略

2.1. 二分查找

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
def binary_search(array, val):
    if not array:
        return -1
    beg = 0
    end = len(array)-1
    while beg <= end:
        mid = int((beg+end)/2)
        if array[mid] == val:
            return val
        elif array[mid] > val:
            end = mid-1
        else:
            beg = mid+1
    return -1


a = list(range(10))

# 正常值
assert binary_search(a, 1) == 1
assert binary_search(a, -1) == -1

# 异常值
assert binary_search(None, 1) == -1

# 边界值
assert binary_search(a, 0) == 0

3. 排序

3.1. 基本排序

3.1.1. 冒泡

对一个数组进行n-1 轮迭代，每次比较相邻两个元素， 如果相邻的元素前者大于后者，就交换它们

  • 时间复杂度：O(n²)
  • 空间复杂度：O(1)
  • 稳定性：稳定

3.1.2. 选择

每次我们找到最小的元素插入迭代的起始位置，这样每个位置从它自己的位置开始它就是最小的了，一圈下来数组就有序了

  • 时间复杂度：O(n²)
  • 空间复杂度：O(1)
  • 稳定性：不稳定

3.1.3. 插入

,每次挑选下一个元素插入已经排序的数组中,初始时已排序数组只有一个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
def insertion_sort(seq):
  """ 每次挑选下一个元素插入已经排序的数组中,初始时已排序数组只有一个元素"""
  n = len(seq)
  print(seq)
  for i in range(1, n):
    value = seq[i]    # 保存当前位置的值，因为转移的过程中它的位置可能被覆盖
    # 找到这个值的合适位置，使得前边的数组有序 [0,i] 有序
    pos = i
    while pos > 0 and value < seq[pos-1]:
      seq[pos] = seq[pos-1]  # 如果前边的元素比它大，就让它一直前移
      pos -= 1
  seq[pos] = value    # 找到了合适的位置赋值就好
  print(seq)
  • 时间复杂度：O(n²)
  • 空间复杂度：O(1)
  • 稳定性：稳定

3.2. 高级排序

3.2.1. 快排

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def partition(array, beg, end):
    pivot_index = beg
    pivot = array[pivot_index]
    left = pivot_index + 1
    right = end - 1    # 开区间，最后一个元素位置是 end-1     [0, end-1] or [0: end)，括号表示开区间

    while True:
        # 从左边找到比 pivot 大的
        while left <= right and array[left] < pivot:
            left += 1

        while right >= left and array[right] >= pivot:
            right -= 1

        if left > right:
            break
        else:
            array[left], array[right] = array[right], array[left]

    array[pivot_index], array[right] = array[right], array[pivot_index]
    return right   # 新的 pivot 位置
  • O(nlog(n))

3.2.2. 归并

  • 分解：将待排序的 n 个元素分成各包含 n/2 个元素的子序列
  • 解决：使用归并排序递归排序两个子序列
  • 合并：合并两个已经排序的子序列以产生已排序的答案
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
28
29
30
31
32
33
34
35
36
37
def merge_sort(seq):
  if len(seq) <= 1:   # 只有一个元素是递归出口
    return seq
  else:
    mid = int(len(seq)/2)
    left_half = merge_sort(seq[:mid])
    right_half = merge_sort(seq[mid:])

    # 合并两个有序的数组
    new_seq = merge_sorted_list(left_half, right_half)
    return new_seq

def merge_sorted_list(sorted_a, sorted_b):
  """ 合并两个有序序列，返回一个新的有序序列

  :param sorted_a:
  :param sorted_b:
  """
  length_a, length_b = len(sorted_a), len(sorted_b)
  a = b = 0
  new_sorted_seq = list()

  while a < length_a and b < length_b:
    if sorted_a[a] < sorted_b[b]:
      new_sorted_seq.append(sorted_a[a]):
      a += 1
    else:
      new_sorted_seq.append(sorted_b[b])
      b += 1

  # 最后别忘记把多余的都放到有序数组里
  if a < length_a:
    new_sorted_seq.extend(sorted_a[a:])
  else:
    new_sorted_seq.extend(sorted_b[b:])

  return new_sorted_seq
  • 时间复杂度：O(nlog₂n)
  • 空间复杂度：O(1)
  • 稳定性：稳定

3.2.3. 基排

基数排序的原理就是，先排元素的最后一位，再排倒数第二位，直到所有位数都排完。这里并不能先排第一位，那样最后依然是无序

1
2
3
4
5
6
7
8
9
10
11
12
def radix_sort(array):
  bucket, digit = [[]], 0
  while len(bucket[0]) != len(array):
    bucket = [[], [], [], [], [], [], [], [], [], []]
    for i in range(len(array)):
      num = (array[i] // 10 ** digit) % 10
      bucket[num].append(array[i])
    array.clear()
    for i in range(len(bucket)):
      array += bucket[i]
    digit += 1
  return array
  • 时间复杂度：O(d(r+n))
  • 空间复杂度：O(rd+n)
  • 稳定性：稳定

3.2.4. 堆排序

1
2
3
4
创建一个堆 H[0……n-1]；
把堆首（最大值）和堆尾互换；
把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
重复步骤 2，直到堆的尺寸为 1

4. 二叉树

  • 节点深度(depth): 节点对应的 level 数字

  • 树的高度(height): 二叉树的高度就是 level 数 + 1，因为 level 从 0开始计算的

  • 树的宽度(width): 二叉树的宽度指的是包含最多节点的层级的节点数

  • 树的 size：二叉树的节点总个数。

    • 一棵 size 为 n 的二叉树高度最多可以是 n，最小的高度是 ⌊lgn⌋+1

  • 在二叉树的第ｉ（ｉ>=１）层最多有２＾(ｉ - １)个结点。

  • 对于任一棵非空二叉树，若其叶结点数为n0，度为2的非叶结点数为n2，则ｎ0 = ｎ2 ＋１

4.1. 满二叉树

如果每个内部节点（非叶节点）都包含两个孩子，就成为满二叉树

一棵深度为$k$且有$2^k-1$个结点的二叉树称为满二叉树

4.2. 完美二叉树(perfect binary tree)

当所有的叶子节点都在同一层就是完美二叉树，毫无间隙填充了 h 层。

4.3. 完全二叉树(complete binary tree)

一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树

完全二叉树的特点是：“叶子节点的位置比较规律”。因此在对数据进行排序或者查找时可以用到它，比如堆排序就使用了它

4.4. 二分查找树(搜索树)

二叉查找树（又叫二叉排序树），它是具有下列性质的二叉树：

  • 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
  • 左、右子树也分别为二叉排序树。
    • “递归定义”

在最好的情况下，二叉排序树的查找效率比较高，是 O(logn)，其访问性能近似于折半查找；

但最差时候会是 O(n)，比如插入的元素是有序的，生成的二叉排序树就是一个链表，这种情况下，需要遍历全部元素才行

4.5. 平衡二叉树

平衡二叉树的提出就是为了保证树不至于太倾斜，尽量保证两边平衡

  • 平衡二叉树要么是一棵空树
  • 要么保证左右子树的高度之差不大于1
  • 子树也必须是一颗平衡二叉树

平衡二叉树在添加和删除时需要进行旋转保持整个树的平衡，内部做了这么复杂的工作后，我们在使用它时，插入、查找的时间复杂度都是**O(logn)**，性能已经相当好了

4.6. 红黑树

红黑树，Red-Black Tree 「RBT」是一个自平衡(不是绝对的平衡)的二叉查找树(BST)

  • 节点是红色或黑色。
  • 根是黑色。
  • 所有叶子都是黑色（叶子是NIL节点）。
  • 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
  • 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点

这些约束确保了红黑树的关键特性：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。

结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树

4.7. B树(B-tree)

B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树（查找路径不只两个）

  • B 树中的每个节点由两部分组成：
    • 关键字（可以理解为数据）
    • 指向孩子节点的指针
  • 每个节点左子树的数据比当前节点都小、右子树的数据都比当前节点的数据大
  • 若根结点不是终端结点，则至少有2棵子树
  • 除根节点以外的所有非叶结点至少有 M/2 棵子树，至多有 M 个子树

B 树的每个节点可以表示的信息更多，因此整个树更加“矮胖”，这在从磁盘中查找数据（先读取到内存、后查找）的过程中，可以减少磁盘 IO 的次数，从而提升查找速度

4.8. B+树

B+ 树是一种树数据结构，通常用于数据库和操作系统的文件系统中。B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。

B+ 树元素自底向上插入，这与二叉树恰好相反

4.9. 哈夫曼树

略

4.10. 二叉树遍历

  • 先(根)序遍历: 先处理根，之后是左子树，然后是右子树
  • 中(根)序遍历: 先处理左子树，之后是根，最后是右子树
  • 后(根)序遍历: 先处理左子树，之后是右子树，最后是根
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# 先序打印二叉树（非递归）
def preOrderTravese(node):
  stack = [node]
  while len(stack) > 0:
    print(node.val)
    if node.right:
      stack.append(node.right)
    if node.left:
      stack.append(node.left)
    node = stack.pop()

# 中序打印二叉树（非递归）
def inOrderTraverse(node):
  stack = []
  pos = node
  while pos or len(stack) > 0:
    if pos:
      stack.append(pos)
      pos = pos.left
    else:
      pos = stack.pop()
      print(pos.val)
      pos = pos.right

# 层序遍历
def layerTraverse(node):
  if not node:
    return None

  queue = []  
  queue.append(node)
  while len(queue) > 0:
    tmp = queue.pop(0)
    print(tmp.val)
    if tmp.left:
      queue.append(tmp.left)
    if tmp.right:
      queue.append(tmp.right)

# 反转二叉树
def reverse(self, subtree):
  if subtree is not None:
    subtree.left, subtree.right = subtree.right, subtree.left
    self.reverse(subtree.left)
    self.reverse(subtree.right)

5. 哈希

5.1. 哈希冲突 (collision)

  • 链接法(chaining，哈希桶)
    • 如果哈希函数选不好的话，可能就导致冲突太多一个链变得太长，这样查找就不再是 O(1) 的了
  • 开放寻址法(open addressing)
    • 基本思想是当一个槽被占用的时候，采用一种方式来寻找下一个可用的槽
    • 线性探查(linear probing)
    • 二次探查(quadratic probing): 当一个槽被占用，以二次方作为偏移量
      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
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      71
      72
      73
      74
      75
      76
      77
      78
      79
      80
      81
          key1：hash(key)+0
          key2：hash(key)+1^2
          key3：hash(key)+2^2
          ```  
        - 双重散列(double hashing): 重新计算 hash 结果。
        - 伪随机序列

      ### 装载因子(load factor)

      > 比如我们上边的例子插入了 8 个元素，哈希表总大小是 13， 它的 load factor 就是 8/13≈0.62。当我们继续往哈希表插入数据的时候，很快就不够用了。 通常当负载因子开始超过 0.8 的时候，就要新开辟空间并且重新进行散列了。

      ### 重哈希(Rehashing)

      > 不同版本的 cpython 使用了不同的策略。python3.3 的策略是扩大为已经使用的槽数目的两倍。开辟了新空间以后，会把原来哈希表里 不为空槽的数据重新插入到新的哈希表里，插入方式和之前一样。这就是 rehashing 操作

      ## 堆

      > 堆（英语：Heap）是计算机科学中的一种特别的完全二叉树。若是满足以下特性，即可称为堆：“**给定堆中任意节点P和C，若P是C的母节点，那么P的值会小于等于（或大于等于）C的值**”
      > - 若母节点的值恒小于等于子节点的值，此堆称为最小堆（min heap）；
      > - 若母节点的值恒大于等于子节点的值，此堆称为最大堆（max heap）
      > 
      > ---
      > 在队列中，调**度程序反复提取队列中第一个作业并运行**，因为实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小，**但具有重要性的作业，同样应当具有优先权**。堆即为解决此类问题设计的一种数据结构

      ## Python

      ### python底层数据结构

      #### 列表和元组

      - 在CPython中，列表被实现为**长度可变的数组**
        - Python在创建这些数组时采用了**指数过分配**，所以**并不是每次操作都需要改变数组的大小**
        - 不幸的是，在普通链表上“代价很小”的其它一些操作在Python中计算复杂度相对过高
          - 利用 list.insert方法在任意位置插入一个元素——复杂度O(N)
          - 利用 list.delete或del删除一个元素——复杂度O(N)

      #### 字典

      - CPython使用**伪随机探测(pseudo-random probing)的散列表(hash table)**作为字典的底层数据结构。由于这个实现细节，只有可哈希的对象才能作为字典的键
        - 从python3.7开始默认Order了

      #### 集合

      - set(): 一种可变的、无序的、有限的集合，其元素是唯一的、不可变的（可哈希的）对象。
      - frozenset(): 一种不可变的、可哈希的、无序的集合，其元素是唯一的，不可变的哈希对象。

      > CPython中集合和字典非常相似。事实上，集合被实现为带有空值的字典，只有键才是实际的集合元素。此外，集合还利用这种没有值的映射做了其它的优化。
      > 
      > 由于这一点，可以快速的向集合中**添加元素、删除元素、检查元素是否存在。**平均时间复杂度为O(1)

      ### deque

      ```py
      # 双向队列
      from collections import deque

      # 保留最后 N 个元素

      >>> q = deque(maxlen=3)
      >>> q.append(1)
      >>> q.append(2)
      >>> q.append(3)
      >>> q
      deque([1, 2, 3], maxlen=3)
      >>> q.append(4)
      >>> q
      deque([2, 3, 4], maxlen=3)

      # O(1)
      deque([1, 2])
      >>> q.append(3)
      >>> q
      deque([1, 2, 3])
      >>> q.appendleft(4)
      >>> q
      deque([4, 1, 2, 3])
      >>> q.pop()
      3
      >>> q
      deque([4, 1, 2])
      >>> q.popleft()

5.2. bisec

  • 查找： bisect(array, item)
  • 插入： insort(array,item)
1
2
3
4
5
6
7
8
9
10
11
12
13
# 数组二分查找
import bisect
 
a = [1,4,6,8,12,15,20]
position = bisect.bisect(a,13)
print(position)
 
# 用可变序列内置的insert方法插入
a.insert(position,13)
print(a)

5
[1, 4, 6, 8, 12, 13, 15, 20]

bisect还有bisect_left，insort_left的用法，和不带left的用法的区别是：当插入的元素和序列中的某一个元素相同时，该插入到该元素的前面（左边，left），还是后面（右边）；如果是查找，则返回该元素的位置还是该元素之后的位置

5.3. heapq

5.4. Priority Queue

6. 参考与摘抄