Python实现堆

堆 (heap) 是一种经过排序的完全二叉树,其中任一非叶子节点的值均不大于(或不小于)其左孩子和右孩子节点的值。

注:定义来自百度百科。

堆,又被为优先队列(priority queue)。尽管名为优先队列,但堆并不是队列。

其他概念解释

  • 最大堆 根结点的键值是所有堆结点键值中最大者。

  • 最小堆 根结点的键值是所有堆结点键值中最小者。

最小堆

Python实现堆

最大堆

Python实现堆

基本功能介绍及实现

在接下来的内容里,我们将逐步介绍堆的具体功能是如何实现的。

堆有两点需要了解,一是堆一般采用完全二叉树;二是堆中的每一个节点都大于其左右子节点(大顶堆),或者堆中每一个节点都小于其左右子节点(小顶堆)。

1. 创建 heap 类

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

2. 添加 get_parent_index 函数

def get_parent_index(self,index):
        #返回父节点的下标
        if index == 0 or index > len(self.data_list) -1:
            return None
        else:
            return (index -1) >> 1

3. 添加 swap 函数

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]

4. 添加 insert 函数

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)

5. 添加 removeMax 函数

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

6. 添加 heapify 函数

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

  

上一篇:[01背包的搜索解法]+[1月13日总结]


下一篇:java:寻找一组数组中的最大值