首页 > 代码库 > 优先队列(堆)

优先队列(堆)

2024-07-09 13:25:08   221人阅读

优先队列(priority queue)是允许至少两种操作的数据结构:Insert及DeleteMin(删除最小者)。相当于队列中的Enqueue、Dequeue操作。

优先队列可以用链表、二叉查找树、二叉堆等实现。

二叉堆

1. 结构性质

堆(heap)是一棵完全被填满的二叉树，有可能的例外是在底层，底层上的元素从左向右填入。这样的树称之为完全二叉树。

一棵高为h的完全二叉树有2h到2h+1-1个节点。完全二叉树的高为logN。

完全二叉树可以用数组来表示，如果从0开始，对于数组中任意i位置的元素，其左儿子在2i+1位置上，右儿子在2i+2位置上，父节点在floor((i-1)/2)位置上。

2.堆序性质

最小堆：对于堆中的每一个节点，其子节点的关键字都大于其的关键字，根节点处为最小值。

最大堆：对于堆中的每一个节点，其子节点的关键字都小于其的关键字，根节点处为最大值。

3.基本的堆操作

Insert：

将要插入的元素X放入到堆末尾，如果不破坏堆的结构，操作完成，否则将X上滤。

如果欲插入的元素一直上滤到根处，那么插入的时间高达O(logN)。平均看来，这种上滤要终止的早。基本上执行一次插入平均需要2.607次比较。

DeleteMin：

对于最小堆，删除根节点，将堆末尾的节点放到根部，然后执行下滤操作。操作的平均操作时间为O(logN)。

最小堆的其它操作：

DecreaseKey(降低关键字的值)：执行上滤操作。

IncreaseKey(增加关键字的值)：执行下滤操作。

Delete：将堆末尾的值放于删除的节点处，执行下滤操作。

BuildHeap(构建堆):

1.执行N次Insert操作。总运行时间为O(N)。

2.从堆末尾节点的父节点开始，向根的方向，依次执行下滤操作。总运行时间为O(N)。

代码：

class MinHeap(object):    def __init__(self):        self.heap=[]        self._count=0    def __len__(self):        return self._count    def insert(self,key):        self.heap.append(key)        self._count+=1        self._up(self._count-1)    def deleteMin(self):        a=self.heap.pop()        self.heap[0]=a        self._count-=1        self._down(0)    def _up(self,i):        if i>0:            parent=(i-1)/2            if self.heap[parent]>self.heap[i]:                self.heap[parent],self.heap[i]=self.heap[i],self.heap[parent]                self._up(parent)    def _down(self,i):        left=2*i+1        right=2*i+2        small=i        if left<self._count and self.heap[i]>self.heap[left]:            small=left        if right<self._count and self.heap[right]<self.heap[small]:            small=right        if small!=i:            self.heap[i],self.heap[small]=self.heap[small],self.heap[i]            self._down(small)

　　


联系
我们