python数据结构——优先级队列，利用最小堆实现

python的堆模块，heapq，默认为小根堆， *** 作：

heapq.heappush(heap,x)   #把x压入堆

heapq.heappop(heap)

heapq.heapreplace(heap,x) #删除最小根，然后压入x

heapq.heapify([2,5,1])  #让列表具有堆特征

用heapq实现大根堆时，入堆和出堆 *** 作，变换为push(-e),  -pop(e) .

from pythonds.trees import BinaryHeap堆heap,可以看做一个完全二叉树的数组对象。常见的堆有二叉堆和斐波那契堆。二叉堆的变体中，根据根节点的最大和最小分为最大堆和最小堆。我们用来存储堆元素的方法依赖堆的有序性：对于堆中任意元素x，x及其父元素p，总是有p<=x。完全二叉树: 除了底层，其他层的节点都是满的。在最底层，从左往右填充节点。实现优先级队列的经典方法是二叉堆，即一棵用列表来表达的二叉树。父节点下标为i，子节点的下标为2*i，2*i+1。节点m的父节点为m/2。优先级队列的插入和删除。插入：先插入到列表最后，然后上浮。删除：最后一个元素调换到根节点，将其下沉。

二叉堆的 *** 作7个

BinaryHeap()  #创建空的二叉堆

BuildHeap(list)  根据列表创建二叉堆

insert(k)   插入元素

findMin()    返回最小值

delMin()   返回最小值并删除根节点

isEmpty()   判断堆是否为空

size()   返回堆的元素个数

创建空的二叉堆

class BinaryHeap:
    def __ini__(self):
        self.heapList=[0]
        self.currentsize=0

insert(k)

def insert(self):
        self.heapList.append(k)
        self.currentsize+=1
        self.percUp(self.currentsize)

def percUp(self,i):
        while i//2>0:
            if self.heapList[i] 
 delMin()。问题：移除根节点之后，怎么重建堆的有序性和结构性质。1.把最后一个元素移到根节点，保证结构性质。2.元素下沉，保证有序性。
 
def delMin(self):
        re=self.heapList[1]
        self.heapList[1]=self.heapList[self.currentsize]
        self.currentsize-=1
        self.heapList.pop()
        self.percDown(1)
        return re

def percDown(self,i):
    while i*2<=self.currentsize
        m=minChild(i)
        if self.heapList[m]self.currentsize
        return 2*i
    else:
        if self.heapList[2*i] 
BuildHeap(list) 根据已有的列表创建二叉堆,时间复杂度为O（n）。从倒数第二层的节点开始，每个节点依次下沉，i-=1。
 
def BuildHeap(self,alist):
    self.heapList=[0]+alist[:]
    self.currentsize=len(alist)
    i=len(alist)//2
    while i>0:
        self.percDown(i)
        i=i-1
        
 
 
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5721440.html