二叉堆

堆是一棵具有特定性质的二叉树-完全二叉树。堆的基本要求是堆中所有结点的值必须大于或等于(或小于或等于)其孩子结点的值。除此以外，所有叶子结点都是处于第 h 或 h - 1层（h为树的高度），其实堆也是一个完全二叉树。堆分为最大堆和最小堆。
182339209436216.jpg
使用数组存储 下标从1开始

  • 父节点 = i / 2
  • 左节点 2 * i
  • 右节点 2 * i + 1

使用数组存储 下标从0开始

  • 父节点 = （i-1） / 2
  • 左节点 2 * i + 1

  • 右节点 2 * i + 2

    最大堆实现

    1. class MaxHeap:
    2.   """
    3.   最大堆
    4.   """
    5.   def __init__(self, capacity=20):
    6.       self.data = []
    7.       self.count = 0
    8.       self.capacity = capacity
    10.   #  获取堆的元素个数
    11.   def size(self):
    12.       return self.count
    14.   # 是否为空
    15.   def is_empty(self):
    16.       return self.count == 0
    18.   # 返回堆的数组表示中 一个索引所表示的元素的父节点的索引
    19.   @staticmethod
    20.   def parent(index: int) -> int:
    21.       assert index >= 0, " index 0 无父节点"
    22.       return (index - 1) // 2
    24.   # 返回索引所表示元素的左孩子节点索引
    25.   @staticmethod
    26.   def left_child(index: int) -> int:
    27.       return index * 2 + 1
    29.   # 返回索引所表示元素的右孩子节点索引
    30.   @staticmethod
    31.   def right_child(index: int) -> int:
    32.       return index * 2 + 2
    34.   # 向堆中添加元素
    35.   def insert(self, data: int):
    36.       assert self.count + 1 < self.capacity, "capacity error"
    37.       self.data.append(data)
    38.       self.count += 1
    39.       self.shift_up(self.count-1)
    41.   # 位置交换
    42.   def shift_up(self, index: int):
    43.       # 找到父元素的值和当前值进行比较
    44.       # 大于父元素进行数据交换
    45.       while self.data[self.parent(index)] < self.data[index] and index > 0:
    46.           self.__swap(self.parent(index), index)
    47.           index = self.parent(index)
    49.   # 数据交换
    50.   def __swap(self, i: int, j: int):
    51.       assert 0 <= i <= self.size() - 1 and 0 <= j <= self.size() - 1, "i j error "
    52.       self.data[i], self.data[j] = self.data[j], self.data[i]
    54.   # 取出根节点(最大值)
    55.   def extract_max(self) -> int:
    56.       assert 0 < self.count, "max_heap is empty "
    57.       # 需要去除的数据
    58.       delete_data = self.data[0]
    59.       # 最后一个元素替换到跟
    60.       self.__swap(0, self.count - 1)
    61.       self.count -= 1
    62.       # 删除最后一个数据
    63.       self.data.pop()
    64.       self.shift_down(0)
    65.       return delete_data
    67.   # 从上往下矫正最大堆
    68.   def shift_down(self, index: int):
    69.       # 确保有一个孩子节点
    70.       while self.left_child(index) < self.count:
    71.           j = self.left_child(index)  # 左节点的位置
    72.           # 右孩子大于左孩子
    73.           if (j + 1) <= self.count - 1 and self.data[j + 1] > self.data[j]:
    74.               # 否则左孩子大于右孩子
    75.               j += 1
    77.           # 当前节点和孩子节点最大值做判断
    78.           if self.data[index] >= self.data[j]:
    79.               break
    81.           self.__swap(index, j)
    82.           index = j
    84.   def show_data(self):
    85.       print(self.data)

    最大堆排序

    1. class MaxHeapSort:
    2.   # 最大堆排序
    3.   def __init__(self):
    4.       self.max_heap = MaxHeap()
    6.   def sort(self,data:list):
    7.       [self.max_heap.insert(i) for i in data]
    8.       for i in range(len(data))[::-1]:
    9.           data[i] = self.max_heap.extract_max()

  • 测试

data = [5,6,7,8,9,1,0]
max_heap_sort = MaxHeapSort()
max_heap_sort.sort(data)
print(data)
[0, 1, 5, 6, 7, 8, 9]

replace

取出最大元素后，放入一个新的元素
方案1：先取出最大值 再添加一个新值，期间需要两次O(logn)操作
方案2：堆顶元素替换后直接siftdown 执行一次操作 期间执行一次O(logn)操作

  1.   def replace(self,v:int):
  2.         max_v = self.data[0]
  3.         self.data[0] = v
  4.         self.shift_down(0)
  5.         return max_v

heapify

对任意数组组装成最大堆结构

  1. # 将任意数据组装成堆的结构
  2. def heapify(self):
  3.     # 从最后一个非叶子节点开始 shift_down
  4.     for i in range(self.parent(len(self.data)-1))[::-1]:
  5.         self.shift_down(i)

优化最大堆排序 - 就地排序

  2. class MaxHeapSort:
  3.     # 最大堆就地排序
  4.     def sort(self, data: list):
  5.         # 就地排序
  6.         if len(data) <= 1:
  7.             return
  8.         # 从最后一个非叶子节点开始 shift_down
  9.         # 先构造成一个最大堆
  10.         for i in range(self.parent(len(data) - 1))[::-1]:
  11.             self.shift_down(data, i, len(data))
  12.         # 开始从堆顶替换元素到末尾
  13.         # 然后依次替换并重新整理为堆
  14.         for j in range(len(data))[::-1]:
  15.             data[0], data[j] = data[j], data[0]
  16.             self.shift_down(data, 0, j)
  18.     # 从上往下矫正最大堆
  19.     def shift_down(self, data, index: int, data_len):
  20.         # 确保有一个孩子节点
  21.         while self.left_child(index) < data_len:
  22.             j = self.left_child(index)  # 左节点的位置
  23.             # 右孩子大于左孩子
  24.             if (j + 1) < data_len and data[j + 1] > data[j]:
  25.                 # 否则左孩子大于右孩子
  26.                 j += 1
  28.             # 当前节点和孩子节点最大值做判断
  29.             if data[index] >= data[j]:
  30.                 break
  32.             data[index], data[j] = data[j], data[index]
  33.             index = j
  35.     # 返回索引所表示元素的左孩子节点索引
  36.     @staticmethod
  37.     def left_child(index: int) -> int:
  38.         return index * 2 + 1
  40.     # 返回索引所表示元素的右孩子节点索引
  41.     @staticmethod
  42.     def right_child(index: int) -> int:
  43.         return index * 2 + 2
  45.     # 返回堆的数组表示中 一个索引所表示的元素的父节点的索引
  46.     @staticmethod
  47.     def parent(index: int) -> int:
  48.         assert index >= 0, " index 0 无父节点"
  49.         return (index - 1) // 2