第六章 堆排序总结

第六章 堆排序总结

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

• 第六章总结
• 思考题 6-2（对d叉堆的分析）

---

第六章总结

python函数heap默认的是最小堆
具体内置函数和方法见https://docs.python.org/zh-cn/3/library/heapq.html

思考题 6-2（对d叉堆的分析）

a、 父结点： ( i − 1 ) / / d (i-1)//d (i−1)//d; 子结点： i ∗ d + j i*d+j i∗d+j
b、 Θ ( l o g d n ) Theta(log_dn) Θ(logd​n)

'''6-2 d叉堆'''


def PARENT(i):
    return (i - 1) // 3


def CHILD(i, j):
    return i * 3 + j


# 维护d叉堆的性质
def d_MAX_HEAPIFY(A, i):
    largest = i
    for d in range(1, 4):
        if CHILD(i, d) < len(A) and A[CHILD(i, d)] > A[i]:
            if A[CHILD(i, d)] > A[largest]:
                largest = CHILD(i, d)
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        A = d_MAX_HEAPIFY(A, largest)
    return A


# 构建最大堆
def BUILD_dMAX_HEAPIFY(A):
    for i in range((len(A) - 3) // 3, -1, -1):
        A = d_MAX_HEAPIFY(A, i)
    return A
    # 提取d叉堆的性质


# 最大堆排序
def dHEAPSORT(A):
    BUILD_dMAX_HEAPIFY(A)
    for i in range(len(A) - 1, 0, -1):
        A[0], A[i] = A[i], A[0]
        A[0:i] = d_MAX_HEAPIFY(A[0:i], 0)

    return A


# 提取d叉堆的最大值并返回一个最大堆
# 时间复杂度（O(dlog_d(n))
def d_EXTRACT_MAX(A):
    A = BUILD_dMAX_HEAPIFY(A)
    max = A[0]
    A[0] = A[-1]
    A.pop()
    A = d_MAX_HEAPIFY(A, 0)
    return max, A


# 返回(13, [12, 7, 10, 11, 5, 6, 2, 8, 9, 3, 4, 1])

def d_INCREASE_KEY(A, i, key):
    A = BUILD_dMAX_HEAPIFY(A)
    if A[i] > key:
        print('new key is smaller than current key')
        return A
    A[i] = key
    while i > 0 and A[PARENT(i)] < A[i]:
        A[PARENT(i)], A[i] = A[i], A[PARENT(i)]
        i = PARENT(i)
    return A


# d_INCREASE_KEY(A,3,15)
# 输出[15, 7, 10, 13, 5, 6, 2, 8, 9, 3, 11, 1, 4]

# 在d叉堆上插入一个元素
def d_INSERT(A, key):
    A = BUILD_dMAX_HEAPIFY(A)
    A.append(-float('inf'))
    A = d_INCREASE_KEY(A, len(A) - 1, key)
    return A


A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
print(d_INSERT(A, 14))
# 输出[14, 13, 10, 12, 7, 6, 2, 8, 9, 3, 11, 1, 4, 5]