深圳城市规划设计研究官方网站,电子商务网站搜索引擎设计,贵阳网站备案,大连集团网站建设目录
二、排序算法#xff08;承接第一部分#xff09; 1、堆排序算法——树的基础知识补充 2、树的基本概念 3、二叉树基础知识
#xff08;1#xff09;满二叉树
#xff08;2#xff09;完全二叉树
#xff08;3#xff09;二叉树的存储方式#xff08;表示方式…目录
二、排序算法承接第一部分 1、堆排序算法——树的基础知识补充 2、树的基本概念 3、二叉树基础知识
1满二叉树
2完全二叉树
3二叉树的存储方式表示方式 4、堆排序大根堆、小根堆
1堆排序过程
2构造堆
3挨个出数
5、堆排序——内置模块
6、堆排序应用——topk问题 二、排序算法承接第一部分 1、堆排序算法——树的基础知识补充
树是一种数据结构 比如目录结构树是一种可以递归定义的数据结构树是由n个节点组成的集合 如果n0那这是一颗空树如果n0那存在一个节点作为树的根节点其他节点可以分为m个集合每隔几何本身又是一棵树 2、树的基本概念
根节点、叶子结点例如B、C、H、P、Q等 不能分叉的节点树的深度高度最深有几层图中为4树的度整个树最大节点的度、节点的度F的度为3分了3个叉孩子节点子节点、父节点E为I的父节点、I为E的孩子节点子树 3、二叉树基础知识
度不超过2的树每个节点最多有两个孩子节点两个孩子节点被区分为左孩子节点和右孩子节点
1满二叉树
一个二叉树如果每一个层的节点数都达到最大值则这个二叉树就是满二叉树
2完全二叉树 叶节点只能出现在最下层和次下层并且最下面一层的节点都集中在该层最左边的若干位置的二叉树 3二叉树的存储方式表示方式
链式存储顺序存储堆排序 从图中我们需要找到两个问题
父节点和左孩子节点的编号下标有什么关系 0-1 1-3 2-5 3-7 4-9i - 2i1父节点和右孩子节点的编号下标有什么关系 0-2 1-4 2-6 3-8 4-10i - 2i2 4、堆排序大根堆、小根堆
堆一种特殊的完全二叉树结构大根堆一颗完全二叉树满足任一节点都比其他孩子节点大小根堆一颗完全二叉树满足任一节点都比其他孩子节点小复杂度Onlogn 1堆排序过程
建立堆构造堆得到堆顶元素为最大元素去掉堆顶将堆最后一个元素放到堆顶此时可通过一次调整向下调整使堆有序堆顶元素为第二大元素重复步骤3直到堆变空
Note
如果不是取最后一个元素到堆顶再进行向下调整将会导致不是完全二叉树
2构造堆 先对最后一个非叶子节点进行调整 然后依次继续往上进行调整 3挨个出数
当堆构造好之后在进行挨个出数
import random
import numpy as npdef sift(li, low, high)::param li: 列表:param low: 堆的第一个元素 根:param high: 堆的最后一个元素i low # 此时i指向第一层j 2 * i 1 # 左孩子temp li[low] # 暂存堆顶元素while j high: # 只要j没有超过high# 有右孩子且与左孩子对比 j 1 high 表示右孩子没有越界if j 1 high and li[j 1] li[j]:j j 1 # j指向右孩子if temp li[j]:li[i] li[j]i j # 往下走一层j 2 * i 1else: # temp更大li[i] temp # 把temp放到某一层根部breakelse:li[i] temp # temp不在根节点,跳出循环后,temp放到叶子结点处def head_sort(li):# 首先建堆n len(li)# 寻找父亲节点 i-1//2 in-1for i in range((n - 2) // 2, -1, -1):# i 表示建堆的时候调整的部分根的下标sift(li, i, n - 1)# 建堆完成for i in range(n - 1, -1, -1):# i指向当前堆的最后一个元素li[0], li[i] li[i], li[0] # 堆顶元素和最后一个元素调整sift(li, 0, i - 1) # 调整 此时最后一个元素是i-1li [i for i in range(100)]
random.shuffle(li)
print(li)
head_sort(li)
print(li)5、堆排序——内置模块
Python内置模块——heapqqqueue 优先队列常用函数 heapifyx建堆——小根堆heappushheapitem往里面加元素heappopheap往外弹出一个元素最小的元素
import heapq
import randomli [i for i in range(100)]
random.shuffle(li)print(li)
heapq.heapify(li)
print(li)for i in range(100):print(heapq.heappop(li), end,)
6、堆排序应用——topk问题
现在有n个数设计算法得到前k大的数。kn解决思路 排序后切片 Onlogn冒泡、插入、选择排序Okn堆排序 Onlogk取列表前k个元素建立一个小根堆。堆顶就是目前第k大的数依次向后遍历原列表对于列表中的元素如果小于堆顶则忽略该元素如果大于堆顶则将堆顶更换为该元素并且对堆进行一次调整。遍历列表所有元素后倒序弹出堆顶
例如我们想到找到前5大的数字我们先取前五个数字建立一个小根堆 发现0不能放进去只剩下7、2、4、5 7比1大所以把1换掉在进行小根堆调整 以此类推最后 import randomdef sift(li, low, high)::param li: 列表:param low: 堆的第一个元素 根:param high: 堆的最后一个元素i low # i,j指向层j 2 * i 1 # 左孩子temp li[low] # 暂存堆顶元素while j high: # 只要j没有超过high# 有右孩子且与左孩子对比 j 1 high 表示右孩子没有越界if j 1 high and li[j 1] li[j]:j j 1 # j指向右孩子if temp li[j]:li[i] li[j]i jj 2 * i 1else:li[i] temp # 把temp放到某一层根部breakelse:li[i] temp # temp不在根节点,跳出循环后,temp放到叶子结点处def topK(li, k):前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.返回前k个return heapif __name__ __main__:li [i for i in range(100)]print(li)random.shuffle(li)print(li)print(topK(li, 10))
