Python中的树形数据结构: 二叉堆的应用

2023-04-11 00:00:00 python 数据结构 二叉堆

树形数据结构在计算机科学中非常常见，它可以用来表示层次结构，并且也被广泛应用于各种算法中。Python中的树形数据结构有很多种实现方式，例如普通的树、二叉树、红黑树等等。其中二叉堆是一种重要的树形数据结构，在大量算法中都得到了应用。

二叉堆是一个特殊的二叉树，它满足以下两个条件：

  1. 父节点的键值总是大于等于（最大堆）或小于等于（最小堆）它的子节点的键值。
  2. 二叉堆是一棵完全二叉树，即除了最后一层，其它所有层都是满的，并且最后一层从左到右填满。

在Python中，二叉堆可以用一个数组来表示。数组中的第一个元素通常被认为是根节点，然后按照层次顺序依次存储左子节点和右子节点。这样存储的好处是不需要额外的指针来指向子节点，节省了空间并提高了访问速度。

下面是一个简单的最小堆的实现，用来存储字符串：

class MinHeap:
    def __init__(self):
        self.heap = []

    def parent(self, i):
        return (i - 1) // 2

    def left(self, i):
        return 2 * i + 1

    def right(self, i):
        return 2 * i + 2

    def insert(self, string):
        self.heap.append(string)
        self.heapify_up(len(self.heap) - 1)

    def heapify_up(self, i):
        while i > 0 and self.heap[self.parent(i)] > self.heap[i]:
            self.heap[self.parent(i)], self.heap[i] = self.heap[i], self.heap[self.parent(i)]
            i = self.parent(i)

    def heapify_down(self, i):
        l = self.left(i)
        r = self.right(i)
        smallest = i
        if l < len(self.heap) and self.heap[l] < self.heap[smallest]:
            smallest = l
        if r < len(self.heap) and self.heap[r] < self.heap[smallest]:
            smallest = r
        if smallest != i:
            self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
            self.heapify_down(smallest)

    def pop_min(self):
        if len(self.heap) == 0:
            return None
        min_val = self.heap[0]
        self.heap[0] = self.heap[-1]
        del self.heap[-1]
        self.heapify_down(0)
        return min_val

    def build_heap(self, arr):
        self.heap = arr
        for i in range(len(arr) // 2, -1, -1):
            self.heapify_down(i)

在上面的代码中，我们实现了插入、删除最小元素、建立堆等基本操作。其中heapify_up和heapify_down两个函数分别用来保持堆的性质。heapify_up函数用于插入操作中，将新插入的元素向上移动直到达到正确的位置；heapify_down函数用于删除操作中，将新的根节点向下移动直到达到正确的位置。

最后，我们可以测试这个实现的代码：

>>> heap = MinHeap()
>>> heap.insert("pidancode.com")
>>> heap.insert("is")
>>> heap.insert("a")
>>> heap.insert("great")
>>> heap.insert("website")
>>> heap.pop_min()
'a'
>>> heap.pop_min()
'great'
>>> heap.pop_min()
'is'
>>> heap.pop_min()
'pidancode.com'
>>> heap.pop_min()
'website'
>>> heap.pop_min()
>>> heap.insert("皮蛋编程")
>>> heap.build_heap(["hello", "world", "python"])
>>> heap.pop_min()
'hello'

从输出结果可以看出，二叉堆能够有效地维护一个有序序列，并且在常数时间内找到最小元素。它在排序、优先级队列等算法中都得到了广泛的应用。

相关文章