啊哈算法--堆排序 （python）

向下调整

在·一个最下根堆中，如果将堆顶的元素删除并新增一个数，那么此时就不再符合最小根堆的性质了，因此这个时候就需要将这个数进行向下调整的操作，直到找到合适位置为止。

向下调整代码如下：

# 向下调整代码，初始堆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)

堆排序

堆排序的原理：

1. 建立小根堆
2. 每次删除堆顶元素作为输出或者放入一个新的数组中，直到堆为空为止。

# 删除堆顶的元素
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 = ' ')