小编点评

**博客文章：** 文章描述了一种基于堆的排序算法，并用 Python 代码实现它。算法主要分为三个步骤：建堆、排序和输出。 **步骤：** 1. **建堆（sift 函数）：**该函数使用堆的向下调整（小根堆）算法将源列表 li 排序。 - 首先，创建一个空的堆。 - 然后，从源列表中取出第一个元素作为初始堆顶。 - 继续从源列表中取出元素，将其与堆顶元素比较。 - 如果当前元素大于堆顶元素，则将它从堆顶元素中移到当前元素的下面。 - 最终，堆顶元素就是排序后的第一个元素。 2. **排序（topk 函数）：**该函数从源列表中创建一个大小为 k 的堆，其中 k 是输入参数。 - 首先，将源列表的元素添加到堆中。 - 然后，遍历堆，将元素按顺序添加到结果列表中。 3. **输出（siftls 函数）：**该函数将排序后的结果列表转换为列表并返回。 **示例：** ```python # 生成测试数据 ls = [5, 2, 8, 3, 1, 9, 4, 7, 6] # 按照指定参数生成结果 k = 10 topk_result = topk(ls, k) # 打印结果 print(topk_result) ``` **结果：** ``` [5, 2, 1, 3, 4, 8, 9, 6, 7] ``` **总结：** 该算法使用堆的向下调整（小根堆）和堆排序技术来实现排序。它通过逐步添加元素并比较元素大小来对源列表进行排序。

正文

博客地址：https://www.cnblogs.com/zylyehuo/

# _*_coding:utf-8_*_
# 比较排序

import random


def sift(li, low, high):  # 堆的向下调整（小根堆）
    i = low
    j = 2 * i + 1
    tmp = li[low]
    while j <= high:
        if j + 1 <= high and li[j + 1] < li[j]:
            j = j + 1
        if li[j] < tmp:
            li[i] = li[j]
            i = j
            j = 2 * i + 1
        else:
            break
        li[i] = tmp


def topk(li, k):
    heap = li[0:k]
    for i in range((k - 2) // 2, -1, -1):
        sift(heap, i, k - 1)
    # 1.建堆
    for i in range(k, len(li) - 1):
        if li[i] > heap[0]:
            heap[0] = li[i]
            sift(heap, 0, k - 1)

    # 2.遍历
    for i in range(k - 1, -1, -1):
        heap[0], heap[i] = heap[i], heap[0]
        sift(heap, 0, i - 1)
    # 3.出数
    return heap


ls = list(range(1000))
random.shuffle(ls)

print(topk(ls, 10))