堆的实现及工程应用(Python)

4 年前 · 来自专栏 Python七号

somenzz

微信公众号「Python七号」和你一起精进。

堆和栈是计算机程序设计中非常重要的数据结构，操作系统和数据库均有非常广泛的应用，掌握好这两种数据结构也可以高效地解决工程问题。今天分享一下在极客专栏学到的堆的实现和工程应用，希望对你有所启发。

堆有两点需要了解，一是堆是一颗完全二叉树，完全二叉树就是只有最后一层有页子节点，而且页子节点是靠左排列的；二是堆中的每一个节点都大于其左右子节点（大顶堆），或者堆中每一个节点都小于其左右子节点（小顶堆）。

上图中，1 和 2 是大顶堆，3 是小顶堆，4 不是堆。

堆的实现

堆是一颗完全二叉树，完全二叉树使用数据存储最节省内存，因为不需要保存左右子节点的指针。

图中第一个位置不存储数据，是为了方便计算，其实第一个位置也可以存储数据，计算时下标加 1 即可。

def __init__(self):
        初始化一个空堆，使用数组来在存放堆元素，节省存储
        self.data_list = []

堆还要实现的功能有： 1. 插入一个元素。 2. 删除堆顶元素。

插入一个元素

先来实现插入一个元素，插入元素的过程中确保堆的两点，一个是确保它是完全二叉树，二是确保它符合大顶堆（小顶堆），本例以大顶堆为例。

完全二叉树使用数组存储，只要在数组的最后插入新元素，然后让其与父节点比较，如果大于父节点，则与父节点交换，直到小于父节点或到达要节点为止。以下两图有助于理解插入过程。

下面是代码实现：

def insert(self,data):
        先把元素放在最后，然后从后往前依次堆化
        这里以大顶堆为例，如果插入元素比父节点大，则交换，直到最后
        self.data_list.append(data)
        index = len(self.data_list) -1 
        parent = self.get_parent_index(index)
        #循环，直到该元素成为堆顶，或小于父节点（对于大顶堆) 
        while parent is not None and self.data_list[parent] < self.data_list[index]:
            #交换操作
            self.swap(parent,index)
            index = parent
            parent = self.get_parent_index(parent)

删除堆顶元素

删除堆顶元素后，将数组最后一个元素放在堆顶位置，然后从上到下进行堆化，这样就可以确保在删除的过程中仍然是一棵完全二叉树。堆化就是查看当前节点与左右子节点进行比较，如果小于子节点，则与其交换，直到满足大顶堆的条件为止。

下面的图片有助于理解删除过程。

代码实现：

def removeMax(self):
        删除堆顶元素，然后将最后一个元素放在堆顶，再从上往下依次堆化
        remove_data = self.data_list[0]
        self.data_list[0] = self.data_list[-1]
        del self.data_list[-1]
        self.heapify(0)
        return remove_data
    def heapify(self,index):
        从上往下堆化，从index 开始堆化操作 (大顶堆)
        total_index = len(self.data_list) -1
        while True:
            maxvalue_index = index
            if 2*index +1 <=  total_index and self.data_list[2*index +1] > self.data_list[maxvalue_index]:
                maxvalue_index = 2*index +1
            if 2*index +2 <=  total_index and self.data_list[2*index +2] > self.data_list[maxvalue_index]:
                maxvalue_index = 2*index +2
            if maxvalue_index == index:
                break
            self.swap(index,maxvalue_index)
            index = maxvalue_index

测试

完整代码

#encoding = utf-8
class heap(object):
    def __init__(self):
        初始化一个空堆，使用数组来在存放堆元素，节省存储
        self.data_list = []
    def get_parent_index(self,index):
        返回父节点的下标
        if index == 0 or index > len(self.data_list) -1:
            return None
        else:
            return (index -1) >> 1 
    def swap(self,index_a,index_b):
        交换数组中的两个元素
        self.data_list[index_a],self.data_list[index_b] = self.data_list[index_b],self.data_list[index_a] 
    def insert(self,data):
        先把元素放在最后，然后从后往前依次堆化
        这里以大顶堆为例，如果插入元素比父节点大，则交换，直到最后
        self.data_list.append(data)
        index = len(self.data_list) -1 
        parent = self.get_parent_index(index)
        #循环，直到该元素成为堆顶，或小于父节点（对于大顶堆) 
        while parent is not None and self.data_list[parent] < self.data_list[index]:
            #交换操作
            self.swap(parent,index)
            index = parent
            parent = self.get_parent_index(parent)
    def removeMax(self):
        删除堆顶元素，然后将最后一个元素放在堆顶，再从上往下依次堆化
        remove_data = self.data_list[0]
        self.data_list[0] = self.data_list[-1]
        del self.data_list[-1]
        self.heapify(0)
        return remove_data
    def heapify(self,index):
        从上往下堆化，从index 开始堆化操作 (大顶堆)
        total_index = len(self.data_list) -1
        while True:
            maxvalue_index = index
            if 2*index +1 <=  total_index and self.data_list[2*index +1] > self.data_list[maxvalue_index]:
                maxvalue_index = 2*index +1
            if 2*index +2 <=  total_index and self.data_list[2*index +2] > self.data_list[maxvalue_index]:
                maxvalue_index = 2*index +2
            if maxvalue_index == index:
                break
            self.swap(index,maxvalue_index)
            index = maxvalue_index
if __name__ == "__main__":
    myheap = heap()