队列和栈

本次讲解的队列与栈，如果你对之前的线性和链式结构顺利掌握了，那么下边的队列和栈就小菜一碟了。因为我们会用前两节讲到的东西来实现队列和栈。 之所以放到一起讲是因为这两个东西很类似，队列是先进先出结构(FIFO, first in first out)， 栈是后进先出结构(LIFO, last in first out)。

生活中的数据结构：

• 队列。没错就是咱平常排队，第一个来的第一个走

队列 Queue

class Queue():
    def __init__(self):
        self.item = DoubleLinkedList()

    def push(self, value):

        self.item.append(value)
    def pop(self):
        value = self.item.top_node().value
        self.item.remove(value)
        return value

用数组实现队列

class Queue:
    def __init__(self, maxsize=4):
        self.item = Array(maxsize)
        self.head = 0
        self.end = 0
        self.maxsize = maxsize

    def push(self, value):
        self.item[self.head % self.maxsize] = value
        self.head += 1

    def pop(self):
        value = self.item[self.end % self.maxsize]
        self.end +=1
        return value

双端队列 Double ended Queue

头尾都能进出

• append
• appendleft
• headnode()
• tailnode()
• remove(node)

栈 Stack

from collections import deque


class Stack():
    def __init__(self):
        self.item = deque()

    def add(self,value):
        self.item.append(value)
    def pop(self):
        return self.item.pop()

哈希表

哈希表是种数据结构，它可以提供快速的插入操作和查找操作。第一次接触哈希表时，它的优点多得让人难以置信。不论哈希表中有多少数据，插入和删除（有时包括侧除）只需要接近常量的时间即0(1）的时间级。

哈希表简单的理解：在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。 哈希表最常见的例子是以学生学号为关键字的成绩表，１号学生的记录位置在第一条，１０号学生的记录位置在第1０条…

哈希表的工作原理

哈希表基于数组的，正因为数组创建后难于扩展某些哈希表被基本填满时，性能下降得非常严重，所以程序虽必须要清楚表中将要存储多少数据（或者准备好定期地把数据转移到更大的哈希表中，这是个费时的过程）

size = 13
h(765) = 765 % size = 11
h(431) = 431 % size = 2
h(96) = 96 % size = 5
h(142) = 142 % size = 12
h(579) = 579 % size = 7
h(226) = 226 % size = 5
h(903) = 903 % size = 6
h(388) = 388 % size = 11

 

哈希冲突 (collision)

这里到插入 226 这个元素的时候，不幸地发现 h(226) = h(96) = 5，不同的 key 通过我们的哈希函数计算后得到的下标一样

解决方法：链接法(chaining)

inserted_index_set = set()
M = 13

def h(key, M=13):
    return key % M

to_insert = [765, 431, 96, 142, 579, 226, 903, 388]
for number in to_insert:
    index = h(number)
    first_index = index
    i = 1
    while index in inserted_index_set:   # 如果计算发现已经占用，继续计算得到下一个可用槽的位置
        print('th({number}) = {number} % M = {index} collision'.format(number=number, index=index))
        index = (first_index +  i*i) % M   # 根据二次方探查的公式重新计算下一个需要插入的位置
        i += 1
    else:
        print('h({number}) = {number} % M = {index}'.format(number=number, index=index))
        inserted_index_set.add(index)

哈希函数

 hash 函数怎么选？ 当然是散列得到的冲突越来越小就好啦，也就是说每个 key 都能尽量被等可能地散列到 m 个槽中的任何一个，并且与其他 key 被散列到哪个槽位无关

装载因子(load factor)

如果继续往我们的哈希表里塞东西会发生什么？空间不够用。这里我们定义一个负载因子的概念(load factor)，其实很简单，就是已经使用的槽数比哈希表大小。 比如我们上边的例子插入了 8 个元素，哈希表总大小是 13， 它的 load factor 就是 $ 8/13 approx 0.62 $。当我们继续往哈希表插入数据的时候，很快就不够用了。 通常当负载因子开始超过 0.8 的时候，就要新开辟空间并且重新进行散列了。

HashTable ADT

lass Slot(object):
    """定义一个 hash 表 数组的槽
    注意，一个槽有三种状态，看你能否想明白
    1.从未使用 HashMap.UNUSED。此槽没有被使用和冲突过，查找时只要找到 UNUSED 就不用再继续探查了
    2.使用过但是 remove 了，此时是 HashMap.EMPTY，该探查点后边的元素扔可能是有key
    3.槽正在使用 Slot 节点
    """
    def __init__(self, key, value):
        self.key, self.value = key, value

class HashTable(object):
    pass

二叉树的遍历

• 先(根)序遍历: 先处理根，之后是左子树，然后是右子树
• 中(根)序遍历: 先处理左子树，之后是根，最后是右子树
• 后(根)序遍历: 先处理左子树，之后是右子树，最后是根

def iter_node1(self, node):
        if node is not None:
            print(node.data)
            self.iter_node1(node.left)
            self.iter_node1(node.right)

二叉树层序遍历

def iter_node2(self, node):
        node_list = [node]

        for node in node_list:
            print(node.data)
            if node.left:
                node_list.append(node.left)
            if node.right:
                node_list.append(node.right)

还有一种方式就是使用一个队列，之前我们知道队列是一个先进先出结构，如果我们按照一层一层的顺序从左往右把节点放到一个队列里， 也可以实现层序遍历：

def layer_trav_use_queue(self, subtree):
  q = Queue()
  q.append(subtree)
  while not q.empty():
    cur_node = q.pop()
    print(cur_node.data)
    if cur_node.left:
      q.append(cur_node.left)
      if cur_node.right:
        q.append(cur_node.right)


from collections import deque
class Queue(object):  # 借助内置的 deque 我们可以迅速实现一个 Queue
    def __init__(self):
        self._items = deque()

    def append(self, value):
        return self._items.append(value)

    def pop(self):
        return self._items.popleft()

    def empty(self):
        return len(self._items) == 0

反转二叉树

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)

实现一个最大堆

class Heap:
    def __init__(self):
        self.items = Array(8)
        self.count = 0

    def add(self, value):
        # 根据count来决定将值暂时赋值到哪块空间
        self.items[self.count] = value
        # 为了保证下一个数据添加时，不替换上一个添加所在的索引的值
        self.count += 1
        # 将本次添加的数据的索引传到 提权函数中
        self.sift_up(self.count - 1)

    def sift_up(self, index):
        if index <= 0:
            return
        else:
            parent = (index - 1) / 2
            if self.items[parent] <= self.items[index]:
                self.items[parent], self.items[index] = self.items[index], self.items[parent]
                self.sift_up(parent)

    def remove(self):
        value = self.items[0]
        self.count -= 1
        self.items[0] = self.items[self.count]
        self.items[self.count] = None
        self.sift_down(0)
        return value

    def sift_down(self, index):
        left = index * 2 + 1
        right = index * 2 + 2

       largest = index
        if right < self.count:
            if self.item[right] > self.item[largest] and self.item[right]> self.item[left]:
                largest = right
            elif self.item[right] >self.item[largest] and self.item[right] < self.item[left]:
                largest = left
            elif self.item[right] < self.item[largest] and self.item[left] >self.item[largest]:
                largest = left
        elif left < self.count:
            if self.item[left] > self.item[largest]:
                largest = left
        if largest != index:
            self.item[index],self.item[largest] = self.item[largest],self.item[index]
            self.siftdown(largest)
    def __iter__(self):
        for i in self.items:
            if i is not None:
                yield i

二叉查找树(BST)

二叉树的一种应用就是来实现堆，我们再看看用二叉查找树(Binary Search Tree, BST)。 前面有章节说到了查找操作，包括线性查找、二分查找、哈希查找等，线性查找效率比较低，二分又要求必须是有序的序列， 为了维持有序插入的代价比较高、哈希查找效率很高但是浪费空间。能不能有一种插入和查找都比较快的数据结构呢？二叉查找树就是这样一种结构，可以高效地插入和查询节点。

BST 定义

二叉查找树是这样一种二叉树结构，它的每个节点的左子节点小于该节点，每个节点的右子节点小于该节点

构造一个 BST

class BST(object):
    def __init__(self, root=None):
        self.root = root

    @classmethod
    def build_from(cls, node_list):
        cls.size = 0
        key_to_node_dict = {}
        for node_dict in node_list:
            key = node_dict['key']
            key_to_node_dict[key] = BSTNode(key)

        for node_dict in node_list:
            key = node_dict['key']
            node = key_to_node_dict[key]
            if node_dict['is_root']:
                root = node
            node.left = key_to_node_dict.get(node_dict['left'])
            node.right = key_to_node_dict.get(node_dict['right'])
            cls.size += 1
        return cls(root)


NODE_LIST = [
    {'key': 60, 'left': 12, 'right': 90, 'is_root': True},
    {'key': 12, 'left': 4, 'right': 41, 'is_root': False},
    {'key': 4, 'left': 1, 'right': None, 'is_root': False},
    {'key': 1, 'left': None, 'right': None, 'is_root': False},
    {'key': 41, 'left': 29, 'right': None, 'is_root': False},
    {'key': 29, 'left': 23, 'right': 37, 'is_root': False},
    {'key': 23, 'left': None, 'right': None, 'is_root': False},
    {'key': 37, 'left': None, 'right': None, 'is_root': False},
    {'key': 90, 'left': 71, 'right': 100, 'is_root': False},
    {'key': 71, 'left': None, 'right': 84, 'is_root': False},
    {'key': 100, 'left': None, 'right': None, 'is_root': False},
    {'key': 84, 'left': None, 'right': None, 'is_root': False},
]
bst = BST.build_from(NODE_LIST)

BST 操作

查找

如何查找一个指定的节点呢，根据定义我们知道每个内部节点左子树的 key 都比它小，右子树的 key 都比它大，所以 对于带查找的节点 search_key，从根节点开始，如果 search_key 大于当前 key，就去右子树查找，否则去左子树查找。 一直到当前节点是 None 了说明没找到对应 key。

 

获取最大和最小 key 的节点

其实还按照其定义，最小值就一直向着左子树找，最大

def _bst_min_node(self, subtree):
        if subtree is None:
            return None
        elif subtree.left is None:   # 找到左子树的头
            return subtree
        else:
            return self._bst_min_node(subtree.left)

    def bst_min(self):
        node = self._bst_min_node(self.root)
        return node.value if node else None

值一直向右子树找，递归查找就行。