社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
在·一个最下根堆中,如果将堆顶的元素删除并新增一个数,那么此时就不再符合最小根堆的性质了,因此这个时候就需要将这个数进行向下调整的操作,直到找到合适位置为止。
向下调整代码如下:
# 向下调整代码,初始堆h为小根堆
def siftdown(i): # 从堆的i结点开始向下调整, 注意i结点的子结点为2*i和2*i+1
global t
flag = 0 # 用于判断是否需要向下调整
while i*2 <= n and flag == 0:
if h[i] > h[2*i]: # 首先判断它与左孩子的关系, 并用t记录较小的节点编号
t = 2*i
else:
t = i
if i*2+1 <= n:
if h[t] > h[2*i+1]: # 如果有右孩子,且右孩子更小,更新较小的值
t = 2*i + 1
if t != i: # 如果最小结点不是自己本身, 说明子结点中有比父结点更小的值
h[t], h[i] = h[i], h[t] # 进行交换
i = t # 从t开始继续向下调整
else: # 否则不需要进行向下调整了,因为子结点中没有比父结点更小的值
flag = 1
有向下调整的操作那么就有向上调整的操作:
向上调整代码如下:
# 向上调整代码, 初始堆h为小根堆 ,
def siftup(i): # i的父节点为i//2
flag = 0 # 用于判断是否需要向上调整
if i == 1:
return # 如果i结点为堆顶,就不能继续往上调整了
while i!=1 and flag == 0:
if h[i] < h[i//2]:
h[i], h[i//2] = h[i//2], h[i]
else:
flag = 1
i = i//2
利用向下调整的操作进行堆的创建我们可以从最后一个非叶子结点(n//2)开始到根结点(1),逐个扫描所有结点,根据需要将当前向下调整。该算法的时间复杂度为O(n)
# 创建堆
def create():
# 从最后一个叶子结点依次向下调整
for s in range(n//2,0,-1):
siftdown(s)
return
利用向上调整的操作进行堆的创建,可以直接从结点1到n依次向上调整,该算法的时间复杂度为O(NlogN)。
# 创建堆2 从空堆开始,然后依次往推中插入每个元素
def create2():
for s in range(1,n+1):
siftup(s)
堆排序的原理:
# 删除堆顶的元素
def removetop():
global n
t = h[1]
h[1] = h[n]
n -= 1
siftdown(1)
return t
h = [0 for _ in range(101)]
n = 0
# 向下调整代码,初始堆h为小根堆
def siftdown(i): # 从堆的i结点开始向下调整, 注意i结点的子结点为2*i和2*i+1
global t
flag = 0 # 用于判断是否需要向下调整
while i*2 <= n and flag == 0:
if h[i] > h[2*i]: # 首先判断它与左孩子的关系, 并用t记录较小的节点编号
t = 2*i
else:
t = i
if i*2+1 <= n:
if h[t] > h[2*i+1]: # 如果有右孩子,且右孩子更小,更新较小的值
t = 2*i + 1
if t != i: # 如果最小结点不是自己本身, 说明子结点中有比父结点更小的值
h[t], h[i] = h[i], h[t] # 进行交换
i = t # 从t开始继续向下调整
else: # 否则不需要进行向下调整了,因为子结点中没有比父结点更小的值
flag = 1
# 向上调整代码, 初始堆h为小根堆 ,
def siftup(i): # i的父节点为i//2
flag = 0 # 用于判断是否需要向上调整
if i == 1:
return # 如果i结点为堆顶,就不能继续往上调整了
while i!=1 and flag == 0:
if h[i] < h[i//2]:
h[i], h[i//2] = h[i//2], h[i]
else:
flag = 1
i = i//2
# 删除堆顶的元素
def removetop():
global n
t = h[1]
h[1] = h[n]
n -= 1
siftdown(1)
return t
# 创建堆
def create():
# 从最后一个叶子结点依次向下调整
for s in range(n//2,0,-1):
siftdown(s)
return
# 创建堆2 从空堆开始,然后依次往推中插入每个元素
def create2():
for s in range(1,n+1):
siftup(s)
if __name__ == '__main__':
num = int(input())
n = num
for i in range(1,num+1):
h[i] = int(input())
create2()
for i in range(1, num + 1):
print(h[i], end=' ')
print()
for _ in range(1,num+1):
print(removetop(), end = ' ')
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!