Binary Heap 二叉堆（二）

深藏阁楼爱情的钟 2024-04-27 16:01 130阅读 0赞

## 一、二叉堆 ##

二叉堆本质上是一种**完全二叉树**。

它分为两类：**最大堆和最小堆**。最大堆的任何一个父节点的值都大于或等于它左右孩子节点的值；最小堆的任何一个父节点的值，都小于或等一它左右孩子节点的值。

![5c56911a5fb74d71a41e589679c946d0.png][]

二叉堆虽然是一个完全二叉树，但它的存储方式并不是链式存储，而是顺序存储。换句话说，二叉堆的所有节点都**存储在数组**中。

> 假设"第一个元素"在数组中的索引为i，则父节点和子节点的位置关系如下:
> 
> 索引为i的父节点的下标：(i-1)/2
> 
> 索引为i的左孩子的下标：2\*i+1
> 
> 索引为i的右孩子的下标：2\*i+2

## 二、二叉堆操作 ##

**1、添加节点**

> 1、新元素一律先插入到堆的尾部
> 
> 2、依次向上调整整个堆的结构（一直到根即可)

![ecada072099b4a8da136c7da8f07a4f2.png][]

***元素添加到队尾***

![59439f3164434bddbfc6ab689106090a.png][]

***持续向上移动并交换***

![a323067293b842b2848814274544d754.png][]

![ee7844ba0f704c7c8cc11a17d3c2c9fa.png][]

**如上图所示：**

class BinaryHeap:
        def __init__(self):
            '''初始化数组'''
            self.data = [None]
    
        def get_parent_index(self, index):
            '''
            父节点索引
            :param index:
            :return:
            '''
            # 判断数组是否越界
            if index == 0 or len(self.data) - 1 < index:
                return None
            # 返回父节点  等价于 (index -1)>>1
            return (index -1) // 2
    
        def insert(self, data):
            """
            1. 先把元素放到最后, 然后从后往前依次堆化
            2. 大堆顶为例, 如果插入元素比父节点大, 则交换, 直到最后
            :param data:  插入元素
            :return: 返回数组
            """
            self.data.append(data)
            index = len(self.data) - 1  # 插入元素的下标
            parent = self.get_parent_index(index)
            # 判断父节点不为空，且父节点元素<子节点元素，循环
            while parent is not None and self.data[parent] < self.data[index]:
                # 交换
                self.data[parent], self.data[index] = self.data[index], self.data[parent]
                #元素下标为之前父节点，继续初始化值
                index = parent
                parent = self.get_parent_index(parent)
            return self.data
    
    
    # 使用示例
    
    if __name__ == '__main__':
        #二叉堆对象
        heap = BinaryHeap()
        ll=[100,90,80,70,60,20,33,15,50]
        print(ll)
        #数组
        heap.data=ll
        #添加数据
        print(heap.insert(95))

![85283d06c1844e97a35ca5a0f313d449.png][]

**2、删除节点**

> 1、将堆尾元素替换到顶部（即对顶被替代删除掉)
> 
> 2、依次从根部向下调整整个堆的结构(一直到堆尾即可)

**删除元素100**

![9b1747da8a5f40eb8f0e11c6429ff8fd.png][]

![3d317a4dd35c4f138633ac1604c7646d.png][]

![c91f4c35256542e9a562a878d81f9fca.png][]

![62f9af7effa54d19b91bf04f8e1ef73b.png][]

![60646157eed749b7a2a350166e896e82.png][]

**如上图所示：**

class BinaryHeap:
        def __init__(self):
            '''初始化数组'''
            self.data = [None]
    
        def removeMax(self):
            # 保存删除的元素
            remove_data = self.data[0]
            # 首尾互换参数
            self.data[0] = self.data[-1]
            #删除最后一个
            del self.data[-1]
    
            # 堆化
            self.heapify(0)
      
            return self.data
    
        def heapify(self, index):
            # 从上往下堆化，从index 开始堆化操作 (大顶堆)
            total_index = len(self.data) - 1
            while True:
                maxvalue_index = index
                # 左右子节点索引
                left = 2 * index + 1
                right = 2 * index + 2
                #查找根，左，右中最大值
                if left <= total_index and self.data[left] > self.data[maxvalue_index]:
                    maxvalue_index = left
                if right <= total_index and self.data[right] > self.data[maxvalue_index]:
                    maxvalue_index = right
                if maxvalue_index == index:
                    break
                self.data[index], self.data[maxvalue_index] = self.data[maxvalue_index], self.data[index]
                index = maxvalue_index
    
    
    
    if __name__ == '__main__':
        #二叉堆对象
        heap = BinaryHeap()
        ll=[100,90,80,70,60,20,33,15,50,40]
        print(ll)
        #数组
        heap.data=ll
        #删除最大元素
        print(heap.removeMax())

![0fdfe4771a4144a58c5f0560fc50fa60.png][]

由此得出:Binaey Heap 的 find Min/Max 的时间复杂度为 o(1)，其余时间复杂度为 o(logn)。

[5c56911a5fb74d71a41e589679c946d0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/aace00bc4c0241d39165e67186972bee.png
[ecada072099b4a8da136c7da8f07a4f2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/ab703dab590746dbbbe3ab241408f4b5.png
[59439f3164434bddbfc6ab689106090a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/68c886427a9748fb8c3195412b8f0d39.png
[a323067293b842b2848814274544d754.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/d65be4530ec24948bdf968e4f3e9e9a3.png
[ee7844ba0f704c7c8cc11a17d3c2c9fa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/80766c73e1b04155938fd0c45d42e797.png
[85283d06c1844e97a35ca5a0f313d449.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/30e8e0fec7d249a7a7195f781563fb44.png
[9b1747da8a5f40eb8f0e11c6429ff8fd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/797951c15cac44079a5db455f4d0da82.png
[3d317a4dd35c4f138633ac1604c7646d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/1c488c5b225045deb33e2fbfd8166eb4.png
[c91f4c35256542e9a562a878d81f9fca.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/74da74381378491ca3f126fee3b98e5a.png
[62f9af7effa54d19b91bf04f8e1ef73b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/9ccf40356b7a4b46a58d53a80410deb3.png
[60646157eed749b7a2a350166e896e82.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/826c6c72da03445a84bc80081c200c74.png
[0fdfe4771a4144a58c5f0560fc50fa60.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/363cf71519b94d24ac1c92b826e1554c.png