第四章第一节 堆(优先队列)

文章目录

1. 二叉堆
2. 插入
3. 删除
4. 堆的Python实现

二叉堆

一棵完全二叉树称为一个(最小)堆当每个非叶节点的值均小于其子节点的值；最大堆同理。

完全二叉树具有良好的性质：若将完全二叉树的元素从上到下，从左向右放入数组中AT，则AT[i]的左子节点为AT[2i]、右子节点为AT[2i+1]；

下面介绍二叉堆的几个操作——插入、删除，最小值。而构建堆可通过一系列的插入操作来实现。

插入

要插入一个元素X，首先在下一空虚位置创建一个空节点；若将X放在此空节点处不破坏堆序，则插入完成；否则，将空节点的父节点与空节点交换，以此类推，直到将X放在空节点满足堆序。这种策略称为上滤。

注：实际实现时只需要父节点下移即可。

删除

对于堆的删除，特指删除最小元素，即根节点。删除根节点后，根节点为空，考虑将堆的最后一个元素X放到空节点处，若X放在该空节点不破坏堆序，则将X放在该空节点，然后删除完成；否则，将空节点的子节点较小者与空节点交换，以此类推，直到将X放在空节点满足堆序，这种策略称为下滤。

注：实际实现时只需要子节点上移即可。

堆的Python实现

class Heap():
    def __init__(self, n=0):
        if n==0:
            self._list=[]
        else:
            self._list=[0]*n
        self.len=0
    
    def sort(self):
        val=self._list[0]
        parent, lchild, rchild=0, 1, 2
        while rchild<self.len and val<max(self._list[lchild], self._list[rchild]):
            if self._list[lchild]<self._list[rchild]:
                self._list[parent]=self._list[rchild]
                parent=rchild
            else:
                self._list[parent]=self._list[lchild]
                parent=lchild
            lchild, rchild=2*parent+1, 2*parent+2
        if lchild<self.len and val<self._list[lchild]:
            self._list[parent]=self._list[lchild]
            parent=lchild
        self._list[parent]=val

        child=self.len-1
        parent=(child-1)>>1
        val=self._list[child]
        while child>0 and self._list[parent]<val:
            self._list[child]=self._list[parent]
            child=parent
            parent=(child-1)>>1
        self._list[child]=val
    
    def insert(self, val):
        if self.len==len(self._list):
            self._list.append(val)
        else:
            self._list[self.len]=val
        self.len+=1
        self.sort()
    
    def pop(self):
        retval=None
        if self.len>0:
            retval=self._list[0]
            self.len-=1
            self._list[0]=self._list[self.len]
            self.sort()
        return retval
    
    def print_vals(self):
        buffer=''
        low, high=0, 1
        while high<self.len:
            buffer+=' '*(self.len-high+low)
            for x in self._list[low:high]:
                buffer+='{}  '.format(x)
            buffer+='\n'
            low=high
            high=2*high+1
        for x in self._list[low:high]:
            buffer+='{}  '.format(x)
        buffer+='\n'
        print(buffer)

if __name__=='__main__':
    nums=[1,3,5,2,4,6,9,8,7]
    heap=Heap()
    for x in nums:
        heap.insert(x)
        heap.print_vals()
    for ith in range(len(nums)):
        heap.pop()
        heap.print_vals()

堆的Python实现（指定key）

class pHeap():
    def __init__(self, n=0, key=lambda x: x):
        if n==0:
            self._list=[]
        else:
            self._list=[0]*n
        self.len=0
        self.key=key
    
    def sort(self):
        val=self._list[0]
        parent, lchild, rchild=0, 1, 2
        while rchild<self.len and self.key(val)<max(self.key(self._list[lchild]), self.key(self._list[rchild])):
            if self.key(self._list[lchild])<self.key(self._list[rchild]):
                self._list[parent]=self._list[rchild]
                parent=rchild
            else:
                self._list[parent]=self._list[lchild]
                parent=lchild
            lchild, rchild=2*parent+1, 2*parent+2
        if lchild<self.len and self.key(val)<self.key(self._list[lchild]):
            self._list[parent]=self._list[lchild]
            parent=lchild
        self._list[parent]=val

        child=self.len-1
        parent=(child-1)>>1
        val=self._list[child]
        while child>0 and self.key(self._list[parent])<self.key(val):
            self._list[child]=self._list[parent]
            child=parent
            parent=(child-1)>>1
        self._list[child]=val
    
    def insert(self, val):
        if isinstance(self.key(val), int) is False:
            print('key(val) is not int')
        if self.len==len(self._list):
            self._list.append(val)
        else:
            self._list[self.len]=val
        self.len+=1
        self.sort()
    
    def pop(self):
        retval=None
        if self.len>0:
            retval=self._list[0]
            self.len-=1
            self._list[0]=self._list[self.len]
            self._list[self.len]=retval
            self.sort()
        return retval
    
    def print_vals(self, fn=None):
        buffer=''
        low, high=0, 1
        while high<self.len:
            buffer+=' '*(self.len-high+low)
            for x in self._list[low:high]:
                buffer+='{}:{}  '.format(x, self.key(x))
            buffer+='\n'
            low=high
            high=2*high+1
        for x in self._list[low:high]:
            buffer+='{}:{}  '.format(x, self.key(x))
        buffer+='\n'
        if fn is None:
            print(buffer)
        else:
            fn.write(buffer)
    
    def check(self):
        buffer=''
        no_err=True
        for ith in range(1, self.len):
            if self.key(self._list[(ith-1)>>1])<self.key(self._list[ith]):
                no_err=False
                buffer+='{}:{}-{}:{}\n'.format(self._list[(ith-1)>>1], self.key(self._list[(ith-1)>>1]), self._list[ith], self.key(self._list[ith]))
        buffer+='\n\n'
        if no_err is False:
            print(buffer)
        return no_err
if __name__=='__main__':
    S=[3,2,3,1,2,4,5,5,6,7,7,8,2,3,1,1,1,10,11,5,6,2,4,7,8,5,6]
    times=dict([(x, 0) for x in S])
    for x in S:
        times[x]+=1
    key=lambda x: times[x]
    pheap=pHeap(len(times), key)
    for x in times:
        pheap.insert(x)
    with open('out', 'w') as fn:
        pheap.print_vals(fn)
        for ith in range(143):
            pheap.pop()
            if pheap.check() is False:
                pheap.print_vals(fn)
    correct=[1,2,5,3,6,7,4,8,10,11]
    print(all([x in correct for x in pheap._list[-len(correct):]]))