二叉树

实现一个二叉查找树，并且支持插入、删除、查找操作

from queue import Queue import math class TreeNode: def __init__(self, val=None): self.val = val self.left = None self.right = None self.parent = None class BinarySearchTree: def __init__(self, val_list=[]): self.root = None for n in val_list: self.insert(n) def insert(self, data): """ 插入 :param data: :return: """ assert(isinstance(data, int)) if self.root is None: self.root = TreeNode(data) else: n = self.root while n: p = n if data < n.val: n = n.left else: n = n.right new_node = TreeNode(data) new_node.parent = p if data < p.val: p.left = new_node else: p.right = new_node return True def search(self, data): """ 搜索 返回bst中所有值为data的节点列表 :param data: :return: """ assert(isinstance(data, int)) # 所有搜索到的节点 ret = [] n = self.root while n: if data < n.val: n = n.left else: if data == n.val: ret.append(n) n = n.right return ret def delete(self, data): """ 删除 :param data: :return: """ assert (isinstance(data, int)) # 通过搜索得到需要删除的节点 del_list = self.search(data) for n in del_list: # 父节点为空，又不是根节点，已经不在树上，不用再删除 if n.parent is None and n != self.root: continue else: self._del(n) def _del(self, node): # 1 if node.left is None and node.right is None: # 情况1和2，根节点和普通节点的处理方式不同 if node == self.root: self.root = None else: if node.val < node.parent.val: node.parent.left = None else: node.parent.right = None node.parent = None # 2 elif node.left is None and node.right is not None: if node == self.root: self.root = node.right self.root.parent = None node.right = None else: if node.val < node.parent.val: node.parent.left = node.right else: node.parent.right = node.right node.right.parent = node.parent node.parent = None node.right = None elif node.left is not None and node.right is None: if node == self.root: self.root = node.left self.root.parent = None node.left = None else: if node.val < node.parent.val: node.parent.left = node.left else: node.parent.right = node.left node.left.parent = node.parent node.parent = None node.left = None # 3 else: min_node = node.right # 找到右子树的最小值节点 if min_node.left: min_node = min_node.left if node.val != min_node.val: node.val = min_node.val self._del(min_node) # 右子树的最小值节点与被删除节点的值相等，再次删除原节点 else: self._del(min_node) self._del(node)

实现二叉树前、中、后序以及按层遍历

# Pre-order traversal def pre_order(root: Optional[TreeNode[T]]) -> Generator[T, None, None]: if root: yield root.val yield from pre_order(root.left) yield from pre_order(root.right) # In-order traversal def in_order(root: Optional[TreeNode[T]]) -> Generator[T, None, None]: if root: yield from in_order(root.left) yield root.val yield from in_order(root.right) # Post-order traversal def post_order(root: Optional[TreeNode[T]]) -> Generator[T, None, None]: if root: yield from post_order(root.left) yield from post_order(root.right) yield root.val

堆

实现一个小顶堆、大顶堆、优先级队列

import math import random class BinaryHeap: """ 大顶堆 """ def __init__(self, data=None, capacity=100): self._data = [] self._capacity = capacity if type(data) is list: if len(data) > self._capacity: raise Exception('Heap oversize, capacity:{}, data size:{}'.format(self._capacity, len(data))) self._type_assert(data) self._data = data self._length = len(self._data) def heapify(self): """ 堆化 :return: """ self._heapify(self._data, self._length-1) def _heapify(self, data, tail_idx): """ 堆化内部实现 :param data: 需要堆化的数据 :param tail_idx: 尾元素的索引 :return: """ # heapify data[:tail_idx+1] if tail_idx <= 0: return # idx of the Last Parent node lp = (tail_idx - 1) // 2 for i in range(lp, -1, -1): self._heap_down(data, i, tail_idx) @staticmethod def _heap_down(data, idx, tail_idx): """ 将指定的位置堆化 :param data: 需要堆化的数据 :param idx: data: 中需要堆化的位置 :param tail_idx: 尾元素的索引 :return: """ assert type(data) is list lp = (tail_idx - 1) // 2 # top-down while idx <= lp: # Left and Right Child index lc = 2 * idx + 1 rc = lc + 1 # right child exists if rc <= tail_idx: tmp = lc if data[lc] > data[rc] else rc else: tmp = lc if data[tmp] > data[idx]: data[tmp], data[idx] = data[idx], data[tmp] idx = tmp else: break def insert(self, num): """ 插入 :param num: :return: """ if self._length < self._capacity: if self._insert(self._data, num): self._length += 1 return True return False @staticmethod def _insert(data, num): """ 堆中插入元素的内部实现 :param data: :param num: :return: """ assert type(data) is list assert type(num) is int data.append(num) length = len(data) # idx of New Node nn = length - 1 # bottom-up while nn > 0: p = (nn-1) // 2 if data[nn] > data[p]: data[nn], data[p] = data[p], data[nn] nn = p else: break return True def get_top(self): """ 取堆顶 :return: """ if self._length <= 0: return None return self._data[0] def remove_top(self): """ 取堆顶 :return: """ ret = None if self._length > 0: ret = self._remove_top(self._data) self._length -= 1 return ret @staticmethod def _remove_top(data): """ 取堆顶内部实现 :param data: :return: """ assert type(data) is list length = len(data) if length == 0: return None data[0], data[-1] = data[-1], data[0] ret = data.pop() length -= 1 # length == 0 or == 1, return if length > 1: BinaryHeap._heap_down(data, 0, length-1) return ret @staticmethod def _type_assert(nums): assert type(nums) is list for n in nums: assert type(n) is int @staticmethod def _draw_heap(data): """ 格式化打印 :param data: :return: """ length = len(data) if length == 0: return 'empty heap' ret = '' for i, n in enumerate(data): ret += str(n) # 每行最后一个换行 if i == 2**int(math.log(i+1, 2)+1) - 2 or i == len(data) - 1: ret += '\n' else: ret += ', ' return ret def __repr__(self): return self._draw_heap(self._data)

实现堆排序

class BinaryHeapSort(BinaryHeap): def __init__(self): super(BinaryHeapSort, self).__init__() def sort(self, nums): """ 排序 1. 堆化，大顶堆 2. 排序，从后往前遍历，首尾元素互换，子数组堆化 :param nums: :return: """ assert type(nums) is list length = len(nums) if length <= 1: return self._type_assert(nums) # heapify self._heapify(nums, length-1) # sort for i in range(length-1, 0, -1): nums[0], nums[i] = nums[i], nums[0] self._heap_down(nums, 0, i-1)

利用优先级队列合并 K 个有序数组

求一组动态数据集合的最大 Top K