欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

数据结构与算法(Python版二叉堆的实现)

程序员文章站 2023-11-03 08:13:28
二叉堆操作的实现二叉堆初始化采用一个列表来保存堆数据,其中表首下标为0的项无用,但为了后面代码可以用到简单的整数乘除法,仍保留它。class BinHeap: def __init__(self): self.heapList = [0] self.currentSize = 0insert(key)方法首先,为了保持“完全二叉树”的性质,新key应该添加到列表末尾。会有问题吗?insert(key)方法新key加在列表末尾,显然无法保持“堆”次序,...

二叉堆操作的实现

二叉堆初始化

采用一个列表来保存堆数据,其中表首下标为0的项无用,但为了后面代码可以用到简单的整数乘除法,仍保留它。

class BinHeap:
    def __init__(self):
        self.heapList = [0]
        self.currentSize = 0

insert(key)方法

首先,为了保持“完全二叉树”的性质,新key应该添加到列表末尾。会有问题吗?
数据结构与算法(Python版二叉堆的实现)
新key加在列表末尾,显然无法保持“堆”次序,虽然对其它路径的次序没有影响,但对于其到根的路径可能破坏次序
数据结构与算法(Python版二叉堆的实现)
需要将新key沿着路径来“上浮”到其正确位置,注意:新key的“上浮”不会影响其它路径节点的“堆”次序
数据结构与算法(Python版二叉堆的实现)

二叉堆操作的实现: insert代码

def percUp(self, i):
    while i // 2 > 0:
        if self.heapList[i] < self.heapList[i//2]:
            # 与父节点交换
            self.heapList[i // 2], self.heapList[i] = self.heapList[i], self.heapList[i // 2]
        # 沿路径向上
        i = i // 2

def insert(self, k):
    # 添加到末尾
    self.heapList.append(k)
    self.currentSize = self.currentSize + 1
    # 新key上浮
    self.percUp(self.currentSize)

delMin()方法

  • 移走整个堆中最小的key:根节点heapList[1],为了保持“完全二叉树”的性质,只用最后一个节点来代替根节点。
  • 同样,这么简单的替换,还是破坏了“堆”次序。
  • 解决方法:将新的根节点沿着一条路径“下沉”,直到比两个子节点都小
    数据结构与算法(Python版二叉堆的实现)
    “下沉”路径的选择:如果比子节点大,那么选择较小的子节点交换下沉
    数据结构与算法(Python版二叉堆的实现)
def percDown(self, i):
    while (i*2) <= self.currentSize:
        mc = self.minChild(i)
        if self.heapList[i] > self.heapList[mc]:
            # 交换下沉
            self.heapList[i], self.heapList[mc] = self.heapList[mc], self.heapList[i]

        # 沿路径向下
        i = mc

def midChild(self, i):
    if i * 2 + 1 > self.currentSize:
        # 唯一子节点
        return i * 2
    else:
        if self.heapList[i*2]<self.heapList[i*2+1]:
            return i*2
        else:
            # 返回较小的
            return i*2+1

def delMin(self):
    # 移走栈顶
    retval = self.heapList[1]
    self.heapList[1] = self.heapList[self.currentSize]
    self.currentSize = self.currentSize - 1
    self.heapList.pop()
    # 新顶下沉
    self.percDown(1)
    return retval

buildHeap(lst)方法:从无序表生成“堆”

我们最自然的想法是:用insert(key)方法,将无序表中的数据项逐个insert到堆中,但这么做的总代价是O(nlog n)。其实,用“下沉”法,能够将总代价控制在O(n)
数据结构与算法(Python版二叉堆的实现)

def buildHeap(self, alist):
    # 从最后节点的父节点开始,因叶节点无需下沉
    i = len(alist) // 2
    self.currentSize = len(alist)
    self.heapList = [0] + alist[:]
    print(len(self.heapList), i)
    while (i > 0):
        print(self.heapList, i)
        self.percDown(i)
        i = i - 1
    print(self.heapList, i)

本文地址:https://blog.csdn.net/weixin_39020133/article/details/107060268