利用二叉堆建立一个优先队列。(数组元素结构为一个最小二叉堆)class priorityQueue:
def __init__(self):
self.queue = list()
self.N = 0
def leftChild(self, k):
return k*2+1
def rightChild(self, k):
return k*2+2
def parent(self, k):
return (k-1)//2
def less(self, i, j):
return self.queue[i]<=self.queue[j]
def exch(self, i, j):
self.queue[i], self.queue[j] = self.queue[j], self.queue[i]
#上浮k节点,以最小堆为例子
def swimMin(self, k):
while k>0 and self.less(k, self.parent(k)):
# 当k还没有上浮到根节点,并且k小于它的父节点,则将k上浮到父节点的位置
self.exch(k, self.parent(k))
k = self.parent(k)
#下沉k节点,以最小堆为例子
def sinkMin(self, k):
#下沉到堆底,就停止
while self.leftChild(k)<self.N:
minEle = self.leftChild(k) #先假设左边最小
if self.rightChild(k)<self.N and self.less(self.rightChild(k), minEle):
#如果右孩子更小,更新minEle
minEle = self.rightChild(k)
# 如果两个孩子都比父节点大,就不需要下沉了
if self.less(k, minEle):
break
self.exch(minEle, k)
k = minEle
def append(self, val):
self.N += 1
self.queue.append(val)
self.swimMin(self.N-1)
def pop(self):
if self.N==0:
return float("nan")
Min = self.queue[0]
self.exch(0, self.N-1)
self.queue.pop()
self.N -= 1
self.sinkMin(0)
return Min
class Solution:
def splitArray(self, nums: List[int]) -> int:
ls = [44,55,36,38,3,7,5]
priortyQ = priorityQueue()
for e in ls:
priorityQ.append(e)#每次往优先队列中加入一个元素
print(priortyQ.queue)
print(priortyQ.pop())#弹出一个元素,为优先队列的最小值