python数据结构教程 Day13

本章内容：

1. 利用二叉堆实现优先队列
2. 二叉堆的python实现
3. 二叉查找树及操作

一、优先队列Priority Queue

定义：

优先队列的出队跟队列一样从队首出队。但在优先队列内部，数据项的次序却是由 “优先级”来确定。高优先级的数据项排在队首，而低优先级的数据项则排在后面。

实现方案：

采用二叉堆数据结构实现，可以使出队和入队的复杂度都达到O(logn)。二叉堆的有趣之处在于，其逻辑结构上象二叉树，却是用非嵌套的列表来实现的。最小key排在队首的称为“最小堆min heap”，反之，最大key排在队首的是“最大堆max heap”。

定义其操作：

• ADT BinaryHeap的操作定义如下：
• BinaryHeap()：创建一个空二叉堆对象；
• insert(k)：将新key加入到堆中；
• findMin()：返回堆中的最小项，最小项仍保留在堆中；
• delMin()：返回堆中的最小项，同时从堆中删除；
• isEmpty()：返回堆是否为空；
• size()：返回堆中key的个数；
• buildHeap(list)：从一个key列表创建新堆

实现其操作：

设计：采用完全二叉树，保证堆操作不受数据影响，始终保持在对数数量级上。（左右子树的节点数应当相同）

列表实现完全二叉树的思路：

根节点下标为1（方便后续计算），左子下标为2p，右子为2p+1，父节点为p//2。堆的次序中永远是父节点key小于子节点的key。

二、二叉堆的python实现

最小堆代码实现：

class myPriorityQueue:
    def __init__(self):
        '''
        注意堆顶在heapList[1]
        '''
        self.heapList = [0]
        self.currentSize = 0

    def findmin(self):
        '''
        最小堆堆顶就是最小值
        '''
        return self.heapList[1]
    
    def isEmpty(self):
        '''
        [0]被占用
        '''
        return self.currentSize == 0

    def size(self):
        return self.currentSize

    def insert(self, key):
        '''
        新的key添加到列表的末尾后，要上浮到适当的位置
        来维护堆的次序
        '''
        self.heapList.append(key)
        self.currentSize += 1
        self.percUp(self.currentSize)#调用上浮函数

    def percUp(self,i):
        '''
        上浮函数
        与父节点进行交换（采用python支持的直接交换方式），沿路径向上
        '''
        while i//2 > 0:
            if self.heapList[i] < self.heapList[i//2]:
                self.heapList[i], self.heapList[i//2] = self.heapList[i//2], self.heapList[i]
            i = i//2

    def minchild(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 percDown(self,i):
        '''
        下沉函数
        '''
        while (i*2) < self.currentSize:
            minchild = self.minchild(i)
            if self.heapList[i] > self.heapList[minchild]:
                self.heapList[i], self.heapList[minchild] = self.heapList[minchild], self.heapList[i]
            i = minchild

    def delMin(self):
        '''
        删除最小的元素，每次出队删除根节点，
        用列表的最后一个元素与第一个元素替换，此时堆的次序遭到了破坏
        所以我们要使新的节点下沉，下沉过程中，选择两个孩子中较小的
        进行交换
        '''
        top = self.heapList[1]
        self.heapList[1] = self.heapList[self.currentSize]
        self.currentSize = self.currentSize - 1
        self.heapList.pop() # 列表删除最后一个元素
        self.heapList.percDown(1) #参数是新顶下标
        return top

    def buildHeap(self, alist):
        '''
        从一个无序列表中构建一个堆，逐个insert
        之后再使用下沉法
        '''
        i = len(alist) // 2
        self.currentSize = len(alist)
        self.heapList = [0] + alist[:]
        while(i>0):
            self.percDown(i)
            i = i - 1
            
    def decreaseKey(self,avertex,adistance):
        '''
        更新距离后，引起堆的重排
        '''
        done = False
        i = 1
        myKey = 0
        while not done and i <= self.currentSize:
            if self.heapArray[i][1] == avertex:
                done = True
                myKey = i
            else:
                i = i + 1
        if myKey > 0:
            self.heapList[myKey] = (adistance,self.heapList[myKey][1])
            self.percUp(myKey)

三、二叉查找树Binary Search Tree及其操作

定义：

比父节点小的key都出现在左子树，比父节点大的key都出现在右子树。注意：插入顺序不同，生成的BST也不同。

下面尝试使用BST实现ADT map：

需要两个类，一个BinarySearchTree实现二叉搜索树，一个TreeNode实现BST中的节点。

TreeNode实现

class TreeNode:
    def __init__(self,key,val,left = None, \
        right = None, parent = None):
        self.key = key
        self.payload = val
        self.leftchild = left
        self.rigthchild = right
        self.parent = parent

    def hasLeftChild(self):
        return self.leftchild

    def hasRightChild(self):
        return self.rigthchild

    def isLeftChild(self):
        return self.parent and self.parent.leftchild == self

    def isRightChild(self):
        return self.parent and self.parent.rigthchild == self

    def isRoot(self):
        return not self.parent

    def isLeaf(self):
        return not(self.leftchild or self.rigthchild)

    def hasAnyChildren(self):
        return self.leftchild or self.rigthchild

    def hasBothChildren(self):
        return self.rigthchild and self.leftchild

    def replaceNodeData(self, key, value, lc, rc):
        self.key = key
        self.payload = value
        self.leftchild = lc
        self.rigthchild = rc
        # 以下两步还是必要的，与C++中的指针不同
        # 与父节点建立联系
        if self.hasLeftChild():
            self.leftchild.parent = self
        if self.hasRightChild():
            self.rigthchild.parent = self

    def __iter__(self):
        '''
        实现在for中可以使用迭代循环
        yield是对每次迭代的返回值,
        中序遍历的迭代
        '''
        if self:
            if self.hasLeftChild():
                for elem in self.leftchild:
                    yield elem
            yield self.key
            if self.hasRightChild():
                for elem in self.rigthchild:
                    yield elem

    def findSuccessor(self):
        '''
        找到当前节点的后继，即右子树最下面的节点（中序遍历的后继）
        '''
        succ = None
        if self.hasRightChild():
            succ = self.rigthchild.findMin()
        else:
            #这个分支在调用remove时不会执行
            if self.parent:
                if self.isLeftChild():
                    succ = self.parent
                else:
                    self.parent.rigthchild = None
                    succ = self.parent.findSuccessor()
                    self.parent.rigthchild = self
        return succ
    
    def findMin(self):
        current = self
        while current.hasLeftChild():
            current = current.leftchild
        return current

    def spliceOut(self):
        '''
        摘出节点
        '''
        if self.isLeaf(): # 摘出叶节点
            if self.isLeftChild():
                self.parent.leftchild = None
            else:
                self.parent.rigthchild = None
        elif self.hasAnyChildren(): # 摘出非叶节点
            if self.hasLeftChild():
                if self.isLeftChild():
                    self.parent.leftchild = self.leftchild
                else:
                    self.parent.rigthchild = self.leftchild
                self.leftchild.parent = self.parent
            else:
                if self.isLeftChild():
                    self.parent.leftchild = self.rigthchild
                else:
                    self.parent.rigthchild = self.rigthchild
                self.rigthchild.parent = self.parent
                

BST类实现：

class BinarySearchTree:
    def __init__(self):
        self.root = None # TreeNode类型
        self.size = 0

    def length(self):
        return self.size

    def __len__(self):
        return self.size

    def __iter__(self):
        return self.root.__iter__() # 直接调用TreeNode的__iter__方法

    def put(self,key,val):
        '''
        添加一个键值对元素
        '''
        if self.root:
            self._put(key,val,self.root)
        else:
            self.root = TreeNode(key, val)
        self.size = self.size + 1

    def _put(self,key, value,currentNode):
        '''
        put函数的具体操作放在_put中，递归函数实现在左右子树添加的过程
        '''
        if key < currentNode.key:
            if currentNode.hasLeftChild():
                self._put(key, value, currentNode.leftchild)
            else:
                currentNode.leftchild = TreeNode(key, value, parent=currentNode)
        else:
            if currentNode.hasRightChild():
                self._put(key, value, currentNode.rigthchild)
            else:
                currentNode.rigthchild = TreeNode(key, value, parent=currentNode)

    def __setitem__(self,k,v):
        '''
        可以实现：myZipTree['PKU'] = 100871
        字典添加键值对的方式
        '''
        self.put(k,v)

    def get(self, key):
        '''
        找到树中key所在的节点并取到payload
        '''
        if self.root:
            res = self._get(key, self.root)
            if res:
                return res.payload
            else:
                return None
        else:
            return None

    def _get(self, key, currentNode):
        '''
        get函数的具体操作放在_get函数中
        相同思想递归查找左子和右子树
        '''
        if not currentNode:
            return None
        elif currentNode.key == key:
            return currentNode
        elif currentNode.key >key:
            return self._get(key,currentNode.leftchild)
        else:
            return self._get(key, currentNode.rigthchild)

    def __getitem__(self, key):
        '''
        实现取到value= myTree[key]
        '''
        self.get(key)

    def __contains__(self, key):
        '''
        实现 in 运算符
        '''
        if self._get(key, self.root):
            return True
        else:
            return False

    def delete(self, key):
        '''
        使用_get方法找到要删除的节点，然后调用remove来删除
        找不到节点时提示错误
        '''
        if self.size > 1:
            nodeToRemove = self._get(key, self.root)
            if nodeToRemove:
                self.remove(nodeToRemove)
                self.size = self.size - 1
            else:
                raise KeyError('Error key not in Tree')
        elif self.size == 1 and self.root.key == key:
            self.root = None
            self.size = self.size - 1
        else:
            raise KeyError('Error key not in tree')
    
    def __delitem__(self,key):
        '''
        实现del mytree['PKU']这样的功能
        '''
        self.delete(key)

    def remove(self, currentNode):
        '''
        从BST中remove一个节点，还要求仍然保持BST的性质，分以下3种情形：
        1、这个节点没有子节点
        2、这个节点有1个子节点
        3、这个节点有2个子节点
        '''
        #1、这个节点没有子节点
        if currentNode.isLeaf():
            if currentNode == currentNode.parent.leftchild:
                currentNode.parent.leftchild = None
            else:
                currentNode.parent.rigthchild = None
        #3、这个节点有2个子节点
        elif currentNode.hasBothChildren():
            succ = currentNode.findSuccessor()
            succ.spliceOut() # 将此后继节点从树中删除
            currentNode.key = succ.key
            currentNode.payload = succ.payload
        #2、这个节点有1个子节点
        else:
            # 被删除节点仅有左子
            if currentNode.hasLeftChild():
                # 被删除节点是父节点的左子
                if currentNode.isLeftChild():
                    currentNode.leftchild.parent = currentNode.parent
                    currentNode.parent.leftchild = currentNode.leftchild
                # 被删除节点是父节点的右子
                elif currentNode.isRightChild():
                    currentNode.leftchild.parent = currentNode.parent
                    currentNode.parent.rigthchild = currentNode.leftchild
                # 被删除节点为根节点,左子替换
                else:
                    currentNode.replaceNodeData(currentNode.leftchild.key,\
                        currentNode.leftchild.payload, currentNode.leftchild.leftchild,\
                        currentNode.leftchild.rigthchild)
            # 被删除节点仅有右子
            else:
                # 被删除节点是父节点的左子
                if currentNode.isLeftChild():
                    currentNode.rigthchild.parent = currentNode.parent
                    currentNode.parent.leftchild = currentNode.rigthchild
                # 被删除节点是父节点的右子
                elif currentNode.isRightChild():
                    currentNode.rigthchild.parent = currentNode.parent
                    currentNode.parent.rigthchild = currentNode.right
                # 被删除节点为根节点,无左子右子替换
                else:
                    currentNode.replaceNodeData(currentNode.rigthchild.key,\
                        currentNode.rigthchild.payload, currentNode.rigthchild.leftchild,\
                            currentNode.rigthchild.rigthchild)

其性能决定因素在于二叉搜索树的高度（最大层次），而其高度又受数据项key插入顺序的影响。

❖如果key的列表是随机分布的话，那么大于和小于根节点key的键值大致相等

❖BST的高度就是log₂N（n是节点的个数），同时这样的树就是平衡树（AVL树）

❖put方法最差性能为O(log₂N)。

但key列表分布极端情况就完全不同，按照从小到大顺序插入的话，put方法的性能为O(n)，树会退化为链，其它方法也是类似情况。