使用 Python 的 List(列表)实现:
class Array:
def __init__(self, x):
self.data = list(x)
array1 = Array([1,2,3])
size() —— 数组元素的个数
def size(self):
return len(self.data)
is_empty() —— 判断数组是否为空
def is_empty(self):
return True if not self.data else False
# other ways: 1. self.data == [] ; 2. len(self.data) == 0
at(index) —— 返回对应索引的元素,若越界则报错
def at(self,index):
if index >= len(self.data):
raise IndexError("Array index out of range.")
return self.data[index]
push(item) —— 在数组末尾插入元素
def push(self,item):
self.data.append(item)
insert(index, item) —— 在指定索引中插入元素,并把后面的元素依次后移
def insert(self, index, item):
self.data.insert(index, item)
pop() —— 删除在数组末端的元素,并返回其值
def pop(self):
return self.data.pop()
delete(index) —— 删除指定索引的元素,并把后面的元素依次前移
def delete(self,index):
self.data.pop(index)
remove(item) —— 删除指定值的元素,并返回其索引(即使有多个元素)
def remove(self,item):
indexList=[]
count=0
for i in range(len(self.data)):
if self.data[i-count]==item:
indexList.append(i)
self.data.pop(i-count)
count+=1
return indexList
find(item) —— 寻找指定值的元素并返回其中第一个出现的元素其索引,若未找到则返回 -1
def find(self, item):
if item in self.data:
return self.data.index(item)
else:
return -1
reverse() —— 翻转数组
def reverse(self):
temp = []
size = len(self.data)
for i in range(size):
temp.append(self.data[size-1-i])
self.data = temp
sort() —— 数组排序(升序) O(nlogn)
def sort(self):
return self.data.sort() # self.data.sort(reverse = True) 为降序
单向链表:
class listNode: # 链表中的结点
def __init__(self, x):
self.val = x
self.next = None
class LinkedList: # 链表类
def __init__(self):
self.head = None
l1 = LinkedList()
l1.add(1)
l1.add(2)
size() —— 返回链表中数据元素的个数/链表长度
def size(self):
size = 0
head = self.head
while head:
size += 1
head = head.next
return size
empty() —— 若链表为空则返回一个布尔值 true
def empty(self):
return True if self.head else False
value_at(index) —— 返回第 n 个元素的值(从0开始计算),若索引超过链表长度则报错
def value_at(self, index):
if not self.head:
raise IndexError("Index out of range.")
head = self.head
while index > 0:
if not head:
raise IndexError("Index out of range.")
head = head.next
index -= 1
return head.val
add(value) —— 添加元素到链表的首部
def add(self, value):
new_node = listNode(value)
new_node.next = self.head
self.head = new_node
pop_front() —— 删除首部元素并返回其值,若链表为空则报错
def pop_front(self):
if not self.head:
raise IndexError("Pop from empty list")
value = self.head.val
self.head = self.head.next
return value
append(value) —— 添加元素到链表的尾部
def append(self, value):
new_node = listNode(value)
if not self.head:
self.head = new_node
return
head = self.head
while head.next:
head = head.next
head.next = new_node
pop_back() —— 删除尾部元素并返回其值,若链表为空则报错
def pop_back(self):
if not self.head:
raise IndexError("Pop from empty list")
if not self.head.next:
value = self.head.val
self.head = None
return value
head = self.head
while head.next.next:
head = head.next
value = head.next.val
head.next = None
return value
front() —— 返回首部元素的值,若链表为空则报错
def front(self):
if not self.head:
raise ValueError("Linked list is empty")
return self.head.val
back() —— 返回尾部元素的值,若链表为空则报错
def back(self):
if not self.head:
raise ValueError("Linked list is empty")
head = self.head
while head.next:
head = head.next
return head.val
insert(index, value) —— 插入值到指定的索引,若索引超出链表长度则报错
def insert(self, index, value):
if not self.head:
raise IndexError("Index out of range")
head = self.head
new_node = listNode(value)
if index == 0:
new_node.next = head
self.head = new_node
return
while index - 1 > 0:
head = head.next
if not head:
raise IndexError("Index out of range")
index -= 1
temp = head.next
head.next = new_node
new_node.next = temp
erase(index) —— 删除指定索引的节点,若索引超出链表长度则报错
def erase(self, index):
if not self.head:
raise IndexError("Index out of range")
head = self.head
if index == 0:
self.head = head.next
while index - 1 > 0:
index -= 1
head = head.next
if not head:
raise IndexError("Index out of range")
temp = head.next
head.next = temp.next
reverse() —— 逆序链表
def reverse(self):
prev = None
head = self.head
while head:
temp = head.next
head.next = prev
prev = head
head = temp
self.head = prev
remove(value) —— 删除链表中指定值的第一个元素
def remove(self,value):
if not self.head:
return
head = self.head
if head.val == value:
self.head = head.next
return
while head.next:
if head.next.val == value:
temp = head.next.next
head.next = temp
return
head = head.next
使用数组实现栈(使用 Python 的 list 实现):
class Stack:
def __init__(self):
self.data = []
s1 = Stack()
s1.push(1)
s1.push(2)
push(item) —— 向栈顶添加元素
def push(self, item):
self.data.append(item)
pop() —— 弹出栈顶的元素,若栈为空则报错
def pop(self):
if self.data:
return self.data.pop()
else:
raise PopError("Pop from empty stack.")
peek() —— 返回栈顶的元素(但是不弹出),若栈为空则报错
def peek(self):
if self.data:
return self.data[-1]
else:
raise IndexError("Stack is empty.")
size() —— 返回栈的长度
is_empty() —— 判断栈是否为空
栈也叫堆栈(这里面的堆不是数据结构的堆)栈满足后进先出 LIFO的原则,时间复杂度:压栈、出栈都是 O(1)
使用 Python 中的列表 List 实现:
enqueue(item) —— 将一个元素入队(在队尾添加元素)
def enqueue(self, item):
self.data.append(item)
dequeue() —— 将队首的元素出队,若队列为空则报错
def dequeue(self):
if self.data:
return self.data.pop(0)
else:
raise DequeueError("Queue is empty.")
size() —— 返回队列长度
is_empty() —— 判断队列是否为空
队列满足先进先出 FIFO 的原则。时间复杂度:出队列使用了列表的 pop(0)
方法,故时间复杂度为 O(n);入队列采用了列表的 append()
方法,故时间复杂度为 O(1)
采用循环队列(Circular Queue),可以将出队和入队的时间复杂度都降到 O(1)。循环队列有一个最大长度max_size
,仍然采用列表实现。两个成员变量front
和rear
分别为队首元素和下一个入队的元素在列表中的索引。为了区别队列为空和队列为满,列表大小应为length = max_size + 1
,列表中最多只能有max_size
个队列元素。
当进行入队操作时,先判断队列是否已满:(rear + 1) % length == front,一种方法是已满直接报错,另一种是若队列已满则扩容为原来的两倍。入队时,rear = (rear + 1) % max_size
进行出队操作时,先判断队列是否为空:front == rear,如果为空则报错。出队时,front = (front + 1) % max_size
获得当前队列长度:(rear - front + length) % length
使用循环队列的方法,由于入队和出队操作都是直接通过索引访问列表,所以时间复杂度都是 O(1)
class CircularQueue:
def __init__(self, max_size = 6):
self.data = [None]*(max_size+1)
self.front = 0
self.rear = 0
get_max_size() —— 获得队列的最大长度
def get_max_size(self):
return len(self.data) - 1
enqueue_strict(item) —— 入队操作,如果队列已满则报错
def enqueue_strict(self, item):
if (self.rear+1) % len(self.data) == self.front:
raise SizeError("Queue is full. Unable to enqueue.")
self.data[self.rear] = item
self.rear = (self.rear+1) % len(self.data)
dequeue_strict() —— 出队操作,如果队列为空则报错
def dequeue_strict(self):
if self.front == self.rear:
raise SizeError("Queue is empty. Unable to dequeue.")
item = self.data[self.front]
self.data[self.front] = None
self.front = (self.front + 1) % len(self.data)
enqueue(item) —— 入队操作,如果已满则扩容为原来队列大小的两倍再入队
def enqueue(self, item):
if (self.rear+1) % len(self.data) == self.front:
self.resize(self.get_max_size() * 2)
self.data[self.rear] = item
self.rear = (self.rear+1) % len(self.data)
dequeue() —— 出队操作,检测如果队列大小等于列表大小的1/4,并且列表大小大于等于2,则减小列表大小为原来的一半以节省空间开销
def dequeue(self):
if self.front == self.rear:
raise SizeError("Queue is empty. Unable to dequeue.")
item = self.data[self.front]
self.data[self.front] = None
self.front = (self.front + 1) % len(self.data)
if self.size() == self.get_max_size()//4 and len(self.data) >= 2:
self.resize(self.get_max_size() // 2)
return item
size() —— 返回队列的当前大小
def size(self):
return (self.rear - self.front + len(self.data)) % len(self.data)
is_empty() —— 判断队列是否为空
def is_empty(self):
return self.front == self.rear
双端队列(Deque)与队列的区别就是,元素可以从两端插入,也可以从两端删除;具备队列与栈的特征,但其中的元素不具备FIFO或者LIFO的顺序,插入和删除操作的规律性需要用户自己维持。
双端队列的一些操作实现,使用Python的列表实现,队首(front)为列表的末尾,队尾(rear)为列表的首部:
class Deque:
def __init__(self):
self.data = []
self.data.append(item)
self.data.insert(0, item)
return self.data.pop()
return self.data.pop(0)
class treeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
深度优先搜索(Depth First Search, DFS)(非递归的版本在完整代码中)
前序遍历 PreOrder Traversal:根-左结点-右结点
def preorder(root):
if root is None:
return []
return [root.val] + preorder(root.left) + preorder(root.right)
中序遍历 InOrder Traversal:左结点-根-右结点
后序遍历 PostOrder Traversal:左结点-右结点-根
广度优先搜索(Breadth First Search, BFS)
层次遍历 LevelOrder Traversal
def level_order(root):
if not root:
return []
res = []
nodequeue = [root]
while nodequeue:
root = nodequeue.pop(0)
res.append(root.val)
if root.left:
nodequeue.append(root.left)
if root.right:
nodequeue.append(root.right)
return res
时间复杂度:需要遍历每个结点,故为O(n)
空间复杂度:由于每个结点都要先进行存储再弹出,故空间复杂度为O(n)
二叉树的后序遍历,非递归版本:非递归的后序遍历是 hard 难度,所以专门在这里写一下。有下面几种思路:
前序遍历是“根-左-右”,稍微改一下,就可以变成“根-右-左”,而将最后的结果倒序输出,就是后序遍历“左-右-根”的顺序了。时间复杂度依然为 O(n):
def postorder_wh1(root):
if root is None:
return []
res = []
nodestack = []
while nodestack or root:
if root:
res.append(root.val)
nodestack.append(root)
root = root.right
else:
root = nodestack.pop()
root = root.left
# res1 用来存放 res 的倒序输出,也可以直接使用res[::-1]
res1 = []
for i in range(len(res)):
res1.append(res.pop())
return res1
使用两个栈实现,这个思路也比较易于理解。后序遍历是“左-右-根”,所以对于一个栈来说,应该先push根结点,然后push右结点,最后push左结点:
def postorder_wh2(root):
if root is None:
return []
res = []
nodestack = [root]
while nodestack:
root = nodestack.pop()
res.append(root)
if root.left:
nodestack.append(root.left)
if root.right:
nodestack.append(root.right)
# 此时res中存放了倒序的结点,使用res1将其倒序输出并取结点的值
res1 = []
for i in range(len(res)):
res1.append(res.pop().val)
return res1
二叉搜索树,也叫二叉查找树(Binary Search Tree,BST),特性是每个结点的值都比左子树大,比右子树小。中序遍历是递增的
def find_item(item, root):
if not root:
return None
while root:
if root.val == item:
return root
elif root.val > item:
root = root.left
else:
root = root.right
return None
def find_max(root):
if not root:
return None
while root.right:
root = root.right
return root
def find_min(root):
if not root:
return None
while root.left:
root = root.left
return root
def add_node(value, root):
if not root:
return treeNode(value)
if value > root.val:
root.right = add_node(value, root.right) # 递归插入右子树
elif value < root.val:
root.left = add_node(value, root.left) # 递归插入左子树
else:
pass # 如果value已经存在,则什么也不做
return root
def delete_node(value, root):
if not root:
return None # 说明要删除的元素未找到
if value < root.val:
root.left = delete_node(value, root.left) # 左子树递归删除
elif value > root.val:
root.right = delete_node(value, root.right) # 右子树递归删除
else: # 说明已经找到要删除的结点了
if not root.left: # 只有右子树或者没有子结点
return root.right
elif not root.right: # 只有左子树
return root.left
else: # 有左右两个结点
temp = find_min(root.right) # 在右子树中找到最小的元素
root.val = temp.val
root.right = delete_node(temp.val, root.right)
return root
使用二叉搜索树对某个元素进行查找,虽然平均情况下的时间复杂度是 O(log n),但是最坏情况下(当所有元素都在树的一侧时)的时间复杂度是 O(n)。因此有了平衡查找树(Balanced Search Tree),平均和最坏情况下的时间复杂度都是 O(log n)
平衡因子(Balance Factor, BF)的概念:左子树高度与右子树高度之差
平衡查找树有很多不同的实现方式:
也叫平衡二叉树(Balanced Binary Tree),AVL是提出这种数据结构的数学家。概念是对于所有结点,BF 的绝对值小于等于1,即左、右子树的高度之差的绝对值小于等于1
在各种平衡查找树当中,AVL 树和2-3树已经成为了过去,而红黑树(red-black trees)看似变得越来越受人青睐 —— Skiena
AVL 树在实际中并没有太多的用途,可支持 O(log n) 的查找、插入、删除,它比红黑树严格意义上更为平衡,从而导致插入和删除更慢,但遍历却更快。适合用于只需要构建一次,就可以在不重新构造的情况下读取的情况。
理解2-3查找树是为了更好地理解红黑树做准备。2-3查找树是一颗BST,它的结点既可以是一个2-结点,即含有两个子结点的结点(和普通二叉树一样),也可以是一个3-结点,即自身有两个value,并且含有三个子结点。3-结点的左链接指向的树中的值都小于该结点的值,中链接指向的树中的值介于该结点的两个值之间,右链接指向的树的值都大于该结点的值。一棵完美平衡的2-3树中的所有空结点到根结点的距离是相同的。
为了保持平衡性,对2-3查找树的插入操作需要分为很多种情况进行调整,这里不打算介绍,因为稍后会重点介绍红黑树的插入操作。但是,就算理解了2-3树插入操作的原理,我们离真正的实现还有一段距离,其中一个原因就是我们需要维护两种不同类型的结点,需要大量的代码。
红黑树(Red-Black Tree)是一种平衡查找树的实现方式,就像AVL树也是平衡查找树的一种实现方式一样,但是AVL树对于平衡的要求更加严格,导致插入/删除的时候更慢。红黑树的定义使得它能保持一定的平衡性(不像AVL那么严格的平衡),同时又能有一定的灵活性(flexibility)。
红黑树首先是一个二叉搜索树,同时必须要满足以下四个性质:
(第二条注意一下,定义中所说的叶结点指的是所有为 None 的结点。当我们画一棵正常的二叉树的时候,通常都不会将这些None结点画出来)
当使用上面的定义来判断一棵树是不是红黑树时,只能逐条定义进行判断,并不存在通过这四个规则推导出来的一个通用简明的判定红黑树的规则。可以看到红黑树并没有像AVL那样规定左右子树的高度之差必须小于1,但是,通过红/黑结点的定义以及约束,红黑树也能像AVL那样维持自己的平衡性。红黑树的最大高度是 2log(n)
如果把一个红黑树中的所有结点都涂成黑色,这棵树仍然是一棵红黑树,但是退化成了一棵完美平衡的二叉树,所以可以看到红黑树的性质使得它有了更多的灵活性。
在红黑树中搜索元素和BST是一样的。但是,当进行插入/删除操作的时候,红黑树的性质会被改变,这时,需要通过变色以及旋转的方式来使其恢复红黑树的性质。进行插入/删除操作的时候,第一步还是按照BST的规则将一个结点插入/删除,然后第二步是恢复红黑树的性质。整个操作的时间复杂度是 O(log n)
先介绍一下如何进行旋转,分为两种情况:左旋(left rotation)和右旋(right rotation)。旋转操作之后,二叉搜索树BST的性质仍然不变。旋转的时间复杂度是常数时间。
那么在插入/删除结点之后,如何通过变色和旋转的方法恢复红黑树的性质呢?以插入为例,首先按照BST中插入结点的方式将结点插入到红黑树中,将其着色为红色(之所以着色为红色是为了避免对规则四的破坏,修复规则四要复杂得多,而着色为红色只破坏了规则三)。然后从新插入的结点开始,逐层向上修复那些破坏了红黑树性质的结点。可以分为以下三种情况进行修复:
CASE 1:要修复的红色结点的 cousin 也是红色结点(cousin 就是其父结点的兄弟结点)
这种情况比较容易解决,只需要变色(re-color)就可以。变色之后,图中不再有与规则3冲突的部分,同时每条路径上黑色结点的数量也没有变化。唯一可能出现问题的就是当把图中最上面那个结点变为红色结点之后,它的父结点可能也是红色结点。但是,即便出现这种情况,我们也完成了将问题结点向上转移的工作,接下来只需要继续往上修复问题结点就行了。
CASE 2:要修复的红色结点的 cousin 是黑色结点,并且这两个结点同向(都是左结点/都是右结点)
对于这种情况,需要首先经过一次旋转操作将其转换为 CASE 3 中的情况,然后再按照 CASE 3 进行处理。旋转一次之后,要修复的结点就变为了和它的 cousin 不同向,即 CASE 3
CASE 3:要修复的红色结点的 cousin 是黑色结点,并且这两个结点不同向
这种情况,经过一次旋转操作和一次变色操作就能彻底修复,满则红黑树的性质,不会将问题结点向上层转移。首先,将问题结点的父结点进行右旋,然后进行变色操作,使红色结点的子结点都是黑色,并且不改变每条路径上黑色结点的数量。操作完成之后,图中最上面的结点是黑色,因此肯定不会与上层的结点发生冲突,黑色结点可以是任何结点的子结点。
可以看到,要修复的永远都是红色结点,并且都是修复规则3 —— 红色结点的子结点也是红色结点。在三种修复的情况中,只要开始进行旋转操作(CASE 2 和 CASE 3),那么修复就会在至多两次旋转操作之内结束。而 CASE 1 的变色操作每次会将有问题的结点向上转移两层,所以至多在 O(log n) 时间内就会结束。所以插入/删除操作的时间复杂度:BST的插入/删除时间复杂度 O(log n) + 恢复红黑树性质的调整操作 O(log n),故时间复杂度为 O(log n)
关于红黑树的理解,强烈推荐下面的视频,跟着视频慢慢过一遍能够让自己有一个比较清楚的理解:
B树英文是 B-Tree,所以中文的B树或者B-树都是同一个东西。至于其中的字母B,则不代表任何东西,既不是 Binary,也不是 Balance.
B树是一种多路搜索树,对于一个 m-阶 的B树:
从定义中可以看出,B树和其它的平衡查找树的最大区别就是不再是一个二叉树,每个结点可以存放多个值(key),并且指向多个子结点。具体地说,一个结点中存放的数据结构为:(n,a0,K1,a1,K2,…,Kn,an),其中 n 代表这个结点含有的 key 的个数,Ki 代表存放的key(也就是二叉树中的value,比如2,23,57...),按升序排列,ai 则是指向子结点的指针,并且 ai 指向的子结点中存放的 key 值总是大于 ai 左边的 key 小于 ai 右边的 key(注意是开区间)。比如a1指向的子结点中存放的元素一定介于K1和K2之间。
B树比起平衡搜索树更加矮胖,这样做大大减小了树的高度,在B树中插入时,B树的高度也会增长得很缓慢,因为每一层都可以容纳很多元素。在最好的情况下,每个结点都被填满,即存放了 m - 1 个元素,最好情况下,B树的高度为:
最坏情况下,每个结点只有 d = ⌈m/2⌉ 个子结点,B树的高度为:
由于B树在高度方面有很大优势,因此,对于文件系统以及数据库,B树是一个不错的选择。在这类应用中,磁盘IO的速度已经远远超过了读取到数据之后在内存中进行处理的速度,所以提升速度的关键是减小磁盘IO。如果每读一次结点,都要进行一次磁盘IO,那当然是希望尽量减少读结点的次数,即使在B树种读了一个结点之后会需要在内存中进行多次比较(一个结点里面有很多元素),那样也会快得多。
关于B树,推荐阅读:B-tree - Wikipedia
B树的查找类似于二叉搜索树的查找,在每个结点,找到待查找元素在哪个范围之间,再进入对应的子结点继续比较
插入元素的时候,先找到元素应该插入的位置,此时:
如果该结点存放的元素数量还没有超过最大限制,那么直接将该元素插入该结点
如果该结点已经满了,那就将其分裂(Split)为两个结点:
首先从该结点存放的所有元素以及待插入元素中选出一个中位数;
把小于中位数的元素放在分裂出来的左结点,大于中位数的元素放在右结点;
这个中位数则插入该结点的父结点。如果父结点已满,继续往上分裂;如果没有父结点,则创造一个新的父结点(会增加树的高度)
这个网站提供了B树的可视化操作:BTree Visualization
参考:
B+ 树是B 树的变种。广泛用于各种文件系统和数据库引擎中。B+ 树的定义与B树基本相同,不同的地方在于:
如果一个结点有k个key,那它有k个子结点
子结点中的数据大于等于左边的key小于右边的key
叶结点中以链表(有序)的形式存放了所有的数据,也包含中间结点的key(因此,B+树的搜索总是会到达叶结点,中间结点不保存数据,只是用来索引的)
优先队列(Priority Queue):一种特殊的队列,取出元素的顺序是按照元素的优先级大小,而不是进入队列的先后顺序(在优先级相同的情况下是FIFO)。可以用堆来实现
堆(Heap)/二叉堆(Binary Heap):用数组表示的完全二叉树。性质:从根到任一结点的路径是有序的。
堆最主要的两个操作是插入和删除,以最大堆为例:
堆的建立:从一个序列中建立一个堆,如果每个元素分别插入,时间复杂度是O(nlog n),因此选取另一种方法,先将序列放入数组,再从倒数第二层开始,从左到右/从右到左依次向下调整为堆,直到调整到树根,时间复杂度为 O(n)
和二叉搜索树相比,堆的内存占用更小(使用数组实现);BST必须平衡的情况下才能达到 O(log n) 的复杂度,但是堆的复杂度始终是 O(log n);对于搜索元素,BST更快,堆不是用来搜索元素的,堆的主要操作是快速插入、删除元素,在堆中搜索元素等同于在数组中搜索元素
那优先队列有什么用呢?为什么不直接把元素排序然后再将这个有序数组作为优先队列呢?一个原因是在某些应用中,总数据量太大,无法进行排序,比如一个10亿规模的数据,而我们只想从中找出最大的10个数,有了优先队列,我们只需要一个存储10个数的队列即可
既然使用数组实现,那就不像二叉树那样有指向子结点的指针,所以在堆中如何进行定位呢?实现堆时,规定下标从1开始,那么对于一个下标为i的结点,有:
parent = floor(i / 2)
left = 2*i
right = 2*i + 1
实现一个最大堆:
class MaxHeap:
def __init__(self):
self.data = [None]
def insert(self, value):
self.data.append(value)
index = self.get_size()
# 如果比父结点大并且不是根结点则向上调整
while index > 1 and self.data[index] > self.data[index//2]:
self.data[index], self.data[index//2] = self.data[index//2],self.data[index]
index = index // 2
# 用于删除和创建堆的函数。从当前结点开始向下调整,保证结点往下是一个堆
def sift_down(self, index):
while 2*index <= self.get_size():
# 左子结点的索引
child = 2 * index
# 如果右子结点存在且比左子结点大,则应与右子结点交换
if 2*index + 1 <= self.get_size() and self.data[2*index+1] > self.data[2*index]:
child += 1 # 右子结点的索引
# 如果当前结点的值小于子结点中的较大者,则应继续向下交换,否则结束
if self.data[index] < self.data[child]:
self.data[index], self.data[child] = self.data[child], self.data[index]
index = child
else:
break
# 删除堆顶元素(最大值)
def remove(self):
if self.is_empty():
raise RemoveError("Unable to remove from an empty heap.")
# 用堆的最后一个元素替代堆顶元素,然后删除最后一个元素
self.data[1], self.data[self.get_size()] = self.data[self.get_size()], self.data[1]
self.data.pop()
# 从堆顶向下调整
self.sift_down(1)
def build_heap(self, array):
self.data = [None] + array
index = self.get_size() // 2
# 从倒数第二层开始,从右到左,逐层向上调整。每次调整只需sift_down
while index > 0:
self.sift_down(index)
index -= 1
了解原理,但可以不用使用代码实现。Trie 是取自 Information Retrieval,一般读作“try”以免与数据结构“tree”相混淆。中文叫做前缀树或字典树,主要用于存储字符串,它和集合以及哈希表相比的优势在于:
字典树有以下特点:
并查集,顾名思义,就是实现集合的并、以及查元素属于哪个集合的功能。比如以下并查集:
{0} {1,5,8} {2,3,4,6} {7,9}
常用操作有:
一种最简单的实现并查集的方式是使用线性结构,用数组存储,数组的每个位置存储元素的值,以及该元素所属的集合ID,这个ID是集合中某个元素的数组下标。这样实现Find的时候直接返回该元素的集合ID,实现Union时先判断两个集合ID是否相同,若不同,则将其中一个集合的ID全部换为另一个集合的ID;实现Connected只需要判断两个元素的集合ID是否相同。
但是这种实现方法的一个问题就是Union的时间复杂度过高,Union需要把一个集合中的每一个元素的ID都替换掉,当元素个数很多时,替换次数就会很多
使用树形结构(不是树这种数据结构)表示并查集,每个结点代表一个集合元素,含有一个指向父结点的指针。使用数组实现,数组中每个位置存放该元素的值和父结点在数组中的索引(根结点存放的索引就是自身的索引)。
在树形结构实现的并查集中,Find的实现依然是遍历数组,返回元素的根结点;Union只需要找到两个元素的根结点,如果不同根,将其中一个元素的根结点指向的父结点设置成另一个元素根结点的数组索引。因此Union的复杂度变为了树的高度O(lg n)
使用树形结构解决了Union操作复杂度高的问题,但是还可以继续改进。可以发现当合并两个集合时,是直接将一颗树接到另一个树的根结点上,这样有可能会导致某棵树不平衡,最坏情况下时间复杂度变为线性。解决方法就是在执行Union操作之前,判断要合并的两棵树,只将小的树合并到大的树中,这样可以保持一定的平衡性,将最坏情况下的时间复杂度降至O(lg n)。这种方法需要一个新的数组存储每棵树的大小。
下面用代码实现这种并查集:
class UnionFind:
# 初始化并查集中的元素,默认每个元素的值就是数组下标,每个元素的集合只有自身
def __init__(self, N):
self.data = list(range(N)) # 存储元素的值
self.parent = list(range(N)) # 存储该元素的父结点的数组下标
self.size = [1] * N # 存储以该元素为根的树的大小(树中的元素个数)
self.count = N # 存储集合的个数
def find(self, value): # 返回根结点的下标
index = self.data.index(value)
while self.parent[index] != index:
index = self.parent[index]
return index
def union(self, value1, value2):
root1 = self.find(value1)
root2 = self.find(value2)
if root1 == root2:
return
if self.size[root1] > self.size[root2]:
self.parent[root2] = root1
self.size[root1] += self.size[root2]
else:
self.parent[root1] = root2
self.size[root2] + self.size[root1]
self.count -= 1
def connected(self, value1, value2):
return self.find(value1) == self.find(value2)
用于存储key对应的value,给定key,能够在非常快速的时间内找到value
设计一个散列函数,计算出关键字key对应的函数值hashcode,作为数据对象value的存储地址。对某个关键字进行查找时,通过散列函数得到地址(或者是array的索引),通过索引访问数组直接得到这个key对应的value,实现 O(1) 的时间复杂度。需要解决哈希冲突(Collision)的问题:即两个关键字映射到同一地址。一种解决办法是在产生冲突的地方使用链表存储,会带来新的问题就是如何确定key对应的value是链表中的哪个,所以这种情况下链表中不仅要存储value,也要存储key,也就是需要有两个field,既存储key,也存储value
如果同一个key要插入不同的value,有几种解决方式:一种是新插入的总是覆盖之前的value,一种是允许一个key存在多个value,查找时随机返回一个value,或者使用find_all返回所有value
填充因子:n/N,已填充(已有的key的数量)/总空间;当填充因子变大时,会失去常数时间的效率,所以需要resize:遍历原来的哈希表,re-hash所有的key,再把value存到新的哈希表的对应位置。当填充因子变小时,也需要resize释放内存
散列方法的存储对关键字是随机的,不适用于顺序查找关键字,不适用于最大/最小值查找或范围查找
散列函数最好计算高效,且映射之后对应的地址空间最好分布均匀以减少冲突。举例:
hash_code(key) = (((a*key + b) mod p) mod N)
;p是一个远大于N 的素数(促进均匀分布),N是存储空间的长度(数组的长度)def hash_code(string_a, N):
hash_val = 0
for i in range(len(string_a)):
hash_val = (127 * hash_val + string_a[i]) % 16908799
return hash_val % N
上面已经说了什么是哈希冲突,这里说一下处理哈希冲突的常用方法:
这两种方法存储的时候都要同时存储key和value,这样查找的时候才知道是否命中对应的key
使用拉链法解决哈希冲突;假设key是数字;如果同一个key插入不同的value,则总是覆盖。
class listNode:
def __init__(self, key, value):
self.key = key
self.value = value
self.next = None
class HashTable:
def __init__(self,N):
self.size = N
self.table = [None] * N
def insert(self, key, value):
index = self.hash_code(key)
head = self.table[index]
if not head: # 如果哈希表对应位置还是空的
self.table[index] = listNode(key, value)
else:
while head.next:
head = head.next
head.next = listNode(key, value)
def find(self, key):
index = self.hash_code(key)
head = self.table[index]
if not head:
return None
else:
while head:
if head.key == key:
return head.value
head = head.next
return None
def remove(self, key):
index = self.hash_code(key)
head = self.table[index]
if not head:
return None
else:
prev = None
while head:
if head.key == key:
next_node = head.next
if prev:
prev.next = next_node
return head.value
else:
self.table[index] = head.next
return head.value
else:
prev = head
head = head.next
return None
首先要解决的问题就是使用什么样的数据结构来表示无向图,一种方式是使用邻接矩阵,即一个大小为v*v的矩阵,当i和j之间有边连接时,则Vij为true,这种方式带来的问题就是总是需要用V^2的空间大小来表示一张有V个顶点的图,当图过大时,开销就会很大。
一种比较好的方式是使用邻接表,即使用数组来表示。将顶点的编号0,1,2... 作为数组的索引,数组中每个位置的元素存放一个链表,链表中存储了所有与该索引的顶点相连的顶点的索引,如图所示:
可以看出,使用这种方式,对于一幅图,可能有多种不同的邻接表来表示。对于一幅V个顶点和E条边的图,空间复杂度与V+E成正比,添加一条边的时间复杂度为常数,遍历一个顶点的所有边的时间复杂度与V的度数成正比。
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。