堆排序前传 - 树与二叉树
- 树是一种数据结构（目录结构）
- 树是一种可以递归定义的数据结构
- 树是由 n 个节点组成的集合
- 如果 n = 0，那这是一颗空树
- 如果 n > 0，那存在1个节点作为树的根节点，其它节点可以分为 m 个集合，每个集合本身又是一棵树
堆
- 堆是一种特殊的完全二叉树
- 大根堆：一颗完全二叉树，满足任一节点都比其孩子节点大
- 小根堆，一颗完全二叉树，满足任一节点都比其孩子节点小
堆排序过程
- 1.建立堆
- 2.得到堆顶元素，为最大元素
- 3.去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一次向下调整重新使堆有序
- 4.堆顶元素为第二大元素
- 5.重复步骤3，直到堆变空
# 时间复杂度：O(nlogn)
def sift(lst, low, high):
"""
堆的一次向下调整
:param lst:列表
:param low:堆的根节点位置
:param high:堆的最后一个元素的位置
:return:
"""
i = low # i 最初指向根节点
j = 2 * i + 1 # j 最初指向 i 的左孩子
tmp = lst[low] # 把堆顶存起来
while j <= high: # 只要 j 位置有数
if j + 1 <= high and lst[j + 1] > lst[j]: # 如果右孩子存在并且比左孩子大
j = j + 1 # j 指向右孩子
if lst[j] > tmp:
lst[i] = lst[j]
i = j # 往下看一层
j = 2 * i + 1
else: # tmp 更大，把 tmp 放到 i 的位置上
lst[i] = tmp
break
else:
lst[i] = tmp # 把 tmp 放到叶子结点上
def heap_sort(lst):
n = len(lst)
# 建堆
for i in range((n - 1 - 1) // 2, -1, -1): # 从最后一个元素的父节点开始循环到0
# i 表示建堆的时候调整的部分的根的下标
sift(lst, i, n - 1)
# 挨个出数
for i in range(n - 1, -1, -1): # 循环从最后一个元素到0
lst[0], lst[i] = lst[i], lst[0]
sift(lst, 0, i - 1) # i-1 是新的 high
堆排序应用 - topk 问题
- 现有 n 个数，设计算法得到前 k 大的数。（k < n）
- 解决思路：
- 排序后切片
- 排序 LowB 三人组
- 堆排序思路
- O(nlogk)
- 1.取列表前 k 个元素建立一个小根堆。堆顶就是目前第 k 大的数。
- 2.依次向后遍历愿列表，对于列表中的元素，如果小于堆顶，则忽略该元素；如果大于堆顶，则将堆顶更换为该元素，并且对堆进行一次调整。
- 3.遍历列表所有元素后，倒序弹出堆顶。
def siftUp(lst, low, high):
"""
小根堆的向下调整
:param lst:
:param low:
:param high:
:return:
"""
i = low # i 最初指向根节点
j = 2 * i + 1 # j 最初指向 i 的左孩子
tmp = lst[low] # 把堆顶存起来
while j <= high: # 只要 j 位置有数
if j + 1 <= high and lst[j + 1] < lst[j]: # 如果右孩子存在并且比左孩子大
j = j + 1 # j 指向右孩子
if lst[j] < tmp:
lst[i] = lst[j]
i = j # 往下看一层
j = 2 * i + 1
else: # tmp 更大，把 tmp 放到 i 的位置上
lst[i] = tmp
break
else:
lst[i] = tmp # 把 tmp 放到叶子结点上
def topk(lst, k):
# 建堆
heap = lst[0:k]
for i in range((k - 1 - 1) // 2, -1, -1):
siftUp(heap, i, k - 1)
# 遍历
for i in range(k, len(lst) - 1):
if lst[i] > heap[0]:
heap[0] = lst[i]
siftUp(heap, 0, k - 1)
# 出数
for i in range(k - 1, -1, -1):
heap[0], heap[i] = heap[i], heap[0]
siftUp(heap, 0, i - 1)
return heap
import random
lst = list(range(1000))
random.shuffle(lst)
print(topk(lst, 10))
