数据结构与算法是计算机科学的基础。包括堆、优先队列、各种排序算法（堆排序、冒泡排序、希尔排序）、线段树、Trie树、并查集、AVL树及红黑树。
堆和优先队列
2.1 堆的定义与性质
堆是一种特殊的完全二叉树，其中每个节点的值都大于或等于（或小于或等于）其子节点的值。这种特性使得堆非常适合用于实现优先队列。
- 最大堆：每个父节点的值大于或等于其任何一个子节点的值。
- 最小堆：每个父节点的值小于或等于其任何一个子节点的值。
2.2 堆的实现
堆通常使用数组来实现，父节点的索引为i时，其左子节点为2*i 1，右子节点为2*i 2。
堆的基本操作
- 插入：
- 向堆中添加元素，并维护堆的性质。
- 删除：
- 删除根节点，并用最后一个元素替换根节点，再进行下沉操作。
以下是最大堆的实现示例：
代码语言：javascript复制pythonclass MaxHeap:
def __init__(self):
self.heap = []
def insert(self, val):
self.heap.append(val)
self._bubble_up(len(self.heap) - 1)
def _bubble_up(self, index):
parent = (index - 1) // 2
if index > 0 and self.heap[index] > self.heap[parent]:
self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
self._bubble_up(parent)
def extract_max(self):
if len(self.heap) == 0:
return None
max_val = self.heap[0]
last_val = self.heap.pop()
if len(self.heap) > 0:
self.heap[0] = last_val
self._sift_down(0)
return max_val
def _sift_down(self, index):
largest = index
left = 2 * index 1
right = 2 * index 2
if left < len(self.heap) and self.heap[left] > self.heap[largest]:
largest = left
if right < len(self.heap) and self.heap[right] > self.heap[largest]:
largest = right
if largest != index:
self.heap[index], self.heap[largest] = self.heap[largest], self.heap[index]
self._sift_down(largest)2.3 优先队列的应用
优先队列是一个抽象数据类型，其元素具有优先级。可以使用堆来实现优先队列。常见应用包括：
- CPU任务调度
- 路径查找算法（如Dijkstra算法）
- 实时事件处理
堆排序
3.1 堆排序的原理
堆排序利用堆的性质来排序数组。具体步骤如下：
- 构建最大堆。
- 将根节点（最大值）与最后一个元素交换，并从堆中移除最大值。
- 对新的根节点进行下沉操作，重复步骤2，直到所有元素排列完毕。
3.2 堆排序的实现
以下是堆排序的Python实现：
代码语言：javascript复制pythondef heapify(arr, n, i):
largest = i
left = 2 * i 1
right = 2 * i 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
# Example usage
arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print("Sorted array is:", arr)冒泡排序
4.1 冒泡排序的原理
冒泡排序是一种简单的排序算法。它通过重复遍历待排序的数组，比较相邻的元素并交换它们，使较大的元素逐步“浮”到顶端。
4.2 冒泡排序的实现
以下是冒泡排序的Python实现：
代码语言：javascript复制pythondef bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n-i-1):
if arr[j] > arr[j 1]:
arr[j], arr[j 1] = arr[j 1], arr[j]
swapped = True
if not swapped:
break
# Example usage
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("Sorted array is:", arr)慕课计算机基础课-希尔排序
5.1 希尔排序的原理
希尔排序是对插入排序的优化，采用分组的方式进行排序。初始时将整个序列分成若干个子序列，对每个子序列进行插入排序，然后逐渐减少分组的数量，最终再对整个序列进行一次插入排序。
5.2 希尔排序的实现
以下是希尔排序的Python实现：
代码语言：javascript复制pythondef shell_sort(arr):
n = len(arr)
gap = n // 2 # 初始步长
while gap > 0:
for i in range(gap, n):
temp = arr[i]
j = i
while j >= gap and arr[j - gap] > temp:
arr[j] = arr[j - gap]
j -= gap
arr[j] = temp
gap //= 2
# Example usage
arr = [12, 34, 54, 2, 3]
shell_sort(arr)
print("Sorted array is:", arr)线段树
6.1 线段树的定义与构建
线段树是一种用于存储区间信息的数据结构，特别适合于需要频繁查询和更新区间的场景。线段树由一系列节点组成，每个节点代表一个区间的信息。
构建线段树
线段树的构建过程是递归的，叶子节点表示数组中的元素，非叶子节点表示其左右孩子节点的合并结果。
6.2 线段树的应用
线段树的典型应用包括：
- 区间求和
- 区间最小值/最大值查询
- 动态区间更新
以下是线段树的基本实现示例：
代码语言：javascript复制pythonclass SegmentTree:
def __init__(self, data):
self.n = len(data)
self.tree = [0] * (2 * self.n)
self.build(data)
def build(self, data):
# Build the tree
for i in range(self.n):
self.tree[self.n i] = data[i]
for i in range(self.n - 1, 0, -1):
self.tree[i] = self.tree[i * 2] self.tree[i * 2 1]
def update(self, idx, value):
# Update a value
idx = self.n
self.tree[idx] = value
while idx > 1:
idx //= 2
self.tree[idx] = self.tree[idx * 2] self.tree[idx * 2 1]
def query(self, left, right):
# Query the sum in [left, right)
result = 0
left = self.n
right = self.n
while left < right:
if left & 1:
result = self.tree[left]
left = 1
if right & 1:
right -= 1
result = self.tree[right]
left //= 2
right //= 2
return result
# Example usage
data = [1, 2, 3, 4, 5]
seg_tree = SegmentTree(data)
print("Sum of range (1, 4):", seg_tree.query(1, 4)) # Output: 9
seg_tree.update(2, 10) # Update index 2 to value 10
print("Sum of range (1, 4):", seg_tree.query(1, 4)) # Output: 16慕课计算机基础课-Trie树
7.1 Trie树的定义
Trie树（前缀树）是一种树形数据结构，用于高效地存储字符串集合。每个节点代表一个字符，路径上的节点拼接在一起形成一个字符串。
7.2 Trie树的操作
Trie树支持以下基本操作：
- 插入字符串
- 查找字符串
- 删除字符串
以下是Trie树的基本实现示例：
代码语言：javascript复制pythonclass TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word
def delete(self, word):
def _delete(node, word, depth):
if not node:
return False
if depth == len(word):
if node.is_end_of_word:
node.is_end_of_word = False
return len(node.children) == 0
return False
char = word[depth]
if char in node.children:
should_delete = _delete(node.children[char], word, depth 1)
if should_delete:
del node.children[char]
return len(node.children) == 0
return False
_delete(self.root, word, 0)
# Example usage
trie = Trie()
trie.insert("hello")
print(trie.search("hello")) # Output: True
trie.delete("hello")
print(trie.search("hello")) # Output: False并查集
8.1 并查集的定义
并查集（Union-Find）是一种用于管理不相交集合的数据结构，支持动态连通性问题的高效解决。
8.2 并查集的实现与优化
并查集主要支持两个操作：
- 查找：确定某个元素属于哪个集合。
- 合并：将两个集合合并为一个。
常见的优化策略包括路径压缩和按秩合并。
以下是并查集的基本实现示例：
代码语言：javascript复制pythonclass UnionFind:
def __init__(self, size):
self.parent = list(range(size))
self.rank = [1] * size
def find(self, p):
if self.parent[p] != p:
self.parent[p] = self.find(self.parent[p]) # Path compression
return self.parent[p]
def union(self, p, q):
rootP = self.find(p)
rootQ = self.find(q)
if rootP != rootQ:
# Union by rank
if self.rank[rootP] > self.rank[rootQ]:
self.parent[rootQ] = rootP
elif self.rank[rootP] < self.rank[rootQ]:
self.parent[rootP] = rootQ
else:
self.parent[rootQ] = rootP
self.rank[rootP] = 1
# Example usage
uf = UnionFind(10)
uf.union(1, 2)
print(uf.find(1) == uf.find(2)) # Output: TrueAVL树
9.1 AVL树的定义与性质
AVL树是一种自平衡的二叉搜索树。每个节点的左子树和右子树的高度差（平衡因子）只能是-1、0或1。这种性质保证了AVL树的操作能够在O(log n)的时间复杂度内完成。
9.2 AVL树的操作
AVL树支持以下基本操作：
- 插入：在插入节点后，需要检查并调整树的平衡性。
- 删除：在删除节点后，同样需要检查并调整树的平衡性。
以下是AVL树的基本实现示例：
代码语言：javascript复制pythonclass AVLNode:
def __init__(self, key):
self.key = key
self.height = 1
self.left = None
self.right = None
class AVLTree:
def get_height(self, node):
return node.height if node else 0
def get_balance(self, node):
if not node:
return 0
return self.get_height(node.left) - self.get_height(node.right)
def right_rotate(self, z):
y = z.left
T3 = y.right
y.right = z
z.left = T3
z.height = max(self.get_height(z.left), self.get_height(z.right)) 1
y.height = max(self.get_height(y.left), self.get_height(y.right)) 1
return y
def left_rotate(self, z):
y = z.right
T2 = y.left
y.left = z
z.right = T2
z.height = max(self.get_height(z.left), self.get_height(z.right)) 1
y.height = max(self.get_height(y.left), self.get_height(y.right)) 1
return y
def insert(self, root, key):
if not root:
return AVLNode(key)
elif key < root.key:
root.left = self.insert(root.left, key)
else:
root.right = self.insert(root.right, key)
root.height = 1 max(self.get_height(root.left), self.get_height(root.right)))
balance = self.get_balance(root)
# LL case
if balance > 1 and key < root.left.key:
return self.right_rotate(root)
# RR case
if balance < -1 and key > root.right.key:
return self.left_rotate(root)
# LR case
if balance > 1 and key > root.left.key:
root.left = self.left_rotate(root.left)
return self.right_rotate(root)
# RL case
if balance < -1 and key < root.right.key:
root.right = self.right_rotate(root.right)
return self.left_rotate(root)
return root
# Example usage
avl = AVLTree()
root = None
keys = [10, 20, 30, 40, 50, 25]
for key in keys:
root = avl.insert(root, key)红黑树
10.1 红黑树的定义与性质
红黑树是一种自平衡的二叉搜索树，具有以下性质：
- 节点是红色或黑色。
- 根节点是黑色。
- 每个叶子节点（NIL）是黑色。
- 如果一个节点是红色，则其两个子节点都是黑色（没有两个连续的红色节点）。
- 从任何节点到其每个叶子节点的所有路径都包含相同数量的黑色节点。
这些性质确保了红黑树的高度是O(log n)。
10.2 红黑树的操作
红黑树支持以下基本操作：
- 插入：插入新节点后，需要调整颜色和树的结构以保持红黑性质。
- 删除：在删除节点后，同样需要调整颜色和树的结构。
以下是红黑树的基本实现示例：
代码语言：javascript复制pythonclass RedBlackNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.parent = None
self.color = 'R' # New nodes are red
class RedBlackTree:
def __init__(self):
self.NIL_LEAF = RedBlackNode(0) # Sentinel NIL leaf
self.NIL_LEAF.color = 'B'
self.root = self.NIL_LEAF
def insert(self, key):
new_node = RedBlackNode(key)
new_node.left = self.NIL_LEAF
new_node.right = self.NIL_LEAF
self._insert_node(new_node)
self.fix_insert(new_node)
def _insert_node(self, node):
# Standard BST insertion logic
current = self.root
parent = None
while current != self.NIL_LEAF:
parent = current
if node.key < current.key:
current = current.left
else:
current = current.right
node.parent = parent
if parent is None: # Tree was empty
self.root = node
elif node.key < parent.key:
parent.left = node
else:
parent.right = node
def fix_insert(self, node):
while node != self.root and node.parent.color == 'R':
# Implement fixing the red-black properties here
pass
# Example usage
rbt = RedBlackTree()
values = [10, 20, 30, 15, 25]
for value in values:
rbt.insert(value)
