啥是堆?

堆分为小堆和大堆
小堆就是父节点都小于孩纸节点
大堆相反

每次从堆顶去得的元素都是最小值，但是每次插入元素和取出元素都要进行平衡堆，时间主要消耗在平衡上


Python内置堆函数

注意是原地修改数组的

heap=[1,4,89,3,2,6]

heapq.heapify(heap)  #将数组转化成堆
print(heap)

# heapq.heappush(heap,99)
# print(heapq.heappop(heap))
# print(heapq.heappop(heap))
# print(heapq.heappop(heap))
# print(heapq.heappop(heap))
#print(heapq.heappop(heap))
print(heapq.heappushpop(heap,0))  #放入一个元素push -->pop 并且出一个元素 long-n
print(heap)
print(heapq.heapreplace(heap,-1)) #pop-->push
print(heap)

自己实现一个！


这里用数组实现堆结构,注意 这里建立的是完全二叉树

1、初始化工作【内置操作函数】

为上浮和下沉提供方便的函数

    def __init__(self):
        self.data = []

    def __len__(self):
        return len(self.data)

    def __str__(self):
        return str(self.data)
    def _parent(self,j): #返回父亲节点位置
        return (j-1)//2   # 由父亲计算出孩子 f = 2p+1 2p+2  反推就是p = (2p+1-1)//2   (2p+2-1)//2  

    def _left(self,j):
        return j*2+1

    def _right(self,j):
        return  j*2+2

    def _hasLeft(self,j):  如果计算出来的孩纸节点长度超过数组长度，就判断没有孩纸
        return self._left(j)<len(self)

    def _hasRight(self,j):
        return self._right(j)<len(self)

    def _swap(self,i,j):  交换元素 主要用于删除操作
        self.data[i],self.data[j] = self.data[j],self.data[i]

2、平衡堆

    上浮
    def _upheap(self,j):
        parent = self._parent(j)  #找到j的父亲节点
        if j>0 and self.data[j]<self.data[parent]:   如果j小于父亲，则和父亲换
            self._swap(j,parent)
            self._upheap(parent)  #继续平衡堆 
下沉
 def _downheap(self,j):
#这里建立的是完全二叉树 所以直接看有没有左孩子 如果连左孩子都没有那右孩纸肯定没有
        if self._hasLeft(j):
            left = self._left(j)
            small = left
            if self._hasRight(j):
                right = self._right(j)
                small = min(left,right)

            if self.data[small] < self.data[j]:
                self._swap(small,j)
                self._downheap(small)

3、插入操作
插入元素先插入在堆的最后，然后进行上浮冒泡操作来平衡堆
注意 这里建立的是完全二叉树对数组建树来说完全二叉树是最节省空间的

 def add(self,value):
        self.data.append(value)
        self._upheap(len(self)-1)

4、取堆顶操作
先将堆顶元素和最后一个元素换，然后删除最后一个元素【也就是堆顶元素】
然后将堆顶元素【也就是原来的最后一个元素】下沉

    def remove(self):
        if not self.data:
            raise Exception("error---->empty")

        self._swap(0,len(self)-1)  #和最后一个换
        item = self.data.pop()
        self._downheap(0)
        return item

5、查找最小元素

    def min(self):
        if not self.data:
            raise Exception("error---->empty")
        return self.data[0]

6、完整代码

class MyHeap():
    def __init__(self):
        self.data = []

    def __len__(self):
        return len(self.data)

    def __str__(self):
        return str(self.data)
    def _parent(self,j): #返回父亲节点位置
        return (j-1)//2

    def _left(self,j):
        return j*2+1

    def _right(self,j):
        return  j*2+2

    def _hasLeft(self,j):
        return self._left(j)<len(self)

    def _hasRight(self,j):
        return self._right(j)<len(self)

    def _swap(self,i,j):
        self.data[i],self.data[j] = self.data[j],self.data[i]

    def _upheap(self,j):
        parent = self._parent(j)
        if j>0 and self.data[j]<self.data[parent]:
            self._swap(j,parent)
            self._upheap(parent)

    def _downheap(self,j):
        if self._hasLeft(j):
            left = self._left(j)
            small = left
            if self._hasRight(j):
                right = self._right(j)
                small = min(left,right)

            if self.data[small] < self.data[j]:
                self._swap(small,j)
                self._downheap(small)


    def add(self,value):
        self.data.append(value)
        self._upheap(len(self)-1)

    def min(self):
        if not self.data:
            raise Exception("error---->empty")
        return self.data[0]

    def remove(self):
        if not self.data:
            raise Exception("error---->empty")

        self._swap(0,len(self)-1)  #和最后一个换
        item = self.data.pop()
        self._downheap(0)
        return item