堆排序描述 堆排序是利用堆这种数据结构所设计的一种排序算法。堆实际上是一个完全二叉树结构 。
问：那么什么是完全二叉树呢？答：假设一个二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树 。
我们知道堆是一个完全二叉树了，那么堆又分两种堆：大顶堆 和 小顶堆 它们符合一个重要的性质：
小顶堆满足：Key[i] <= key[2i + 1] && Key[i] <= key[2i + 2] (父节点小于子节点)
大顶堆满足：Key[i] >= key[2i + 1] && Key[i] >= Key[2i + 2] (父节点大于子节点)
大顶堆最大的元素在跟节点，堆的性质决定了大顶堆中节点一定大于等于其子节点，反之，小顶堆的最小元素在根节点。我们来看看大顶堆和小顶堆的示意图:
堆排序基本思想及步骤
堆排序有以下几个核心的步骤：
将待排序的数组初始化为大顶堆，该过程即建堆。
将堆顶元素与最后一个元素进行交换，除去最后一个元素外可以组建为一个新的大顶堆。（获得当前最大的元素 ）
将第二步堆顶元素跟最后一个元素交换后，新建立的堆不是大顶堆，需要重新建立大顶堆。重复上面的流程，直到堆中仅剩下一个元素。
若二叉树的节点数量为l，则二叉树中，最后一个非叶子节点为l//2 -1
建堆代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 class Solution (object def heap_sort (self,nums ): i,l = 0 ,len (nums) self.nums = nums for i in range (l//2 -1 , -1 , -1 ): self.build_heap(i,l-1 ) print (self.nums) print ("--" ) for j in range (l-1 , -1 , -1 ): nums[0 ],nums[j] = nums[j],nums[0 ] self.build_heap(0 ,j-1 ) return nums def build_heap (self,i,l ): ''' 构建大顶堆 ''' nums = self.nums left,right = 2 * i +1 , 2 * i + 2 large_index =i if left <= l and nums[i] < nums[left]: large_index = left if right <= l and nums[left] < nums[right]: large_index = right if large_index != i: nums[i], nums[large_index] = nums[large_index], nums[i] self.build_heap(large_index,l)
输入：arr = [4, 6, 7, 2, 9, 8, 3, 5]，输出：
描述 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
1 2 3 4 5 输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 输入: nums = [1], k = 1 输出: [1]
解法 参考评论区：347. 前 K 个高频元素，直接排序 +堆排序 + 快速排序，Python4种 + Java2种解法~ - 前 K 个高频元素 - 力扣（LeetCode） (leetcode-cn.com)
方法一：直接排序
时间复杂度：O(nlogn)
空间复杂度：O(n)
1 2 3 4 class Solution : def topKFrequent (self, nums: List [int ], k: int ) -> List [int ]: count = collections.Counter(nums) return [item[0 ] for item in count.most_common(k)]
方法二：堆排序1
记录每个数字出现的次数
把数字和对应出现次数放入堆中
返回堆的前k大元素
1 2 3 4 5 6 class Solution : def topKFrequent (self, nums: List [int ], k: int ) -> List [int ]: count = collections.Counter(nums) heap = [(val, key) for key, val in count.items()] return [item[1 ] for item in heapq.nlargest(k, heap)]
方法三：堆排序2
记录每个数字出现的次数
把数字和对应的出现次数放到堆中（小顶堆）
如果堆已满（大小>=k）且当前数的次数比堆顶大，用当前元素替换堆顶元素
返回堆中的数字部分
1 2 3 4 5 6 7 8 9 10 11 class Solution : def topKFrequent (self, nums: List [int ], k: int ) -> List [int ]: count = collections.Counter(nums) heap = [] for key, val in count.items(): if len (heap) >= k: if val > heap[0 ][0 ]: heapq.heapreplace(heap, (val, key)) else : heapq.heappush(heap, (val, key)) return [item[1 ] for item in heap]
NC119 最小的K个数 描述 给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
0 <= k <= input.length <= 10000
0 <= input[i] <= 10000
解法：堆排序 1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution : def GetLeastNumbers_Solution (self, tinput, k ): import heapq heapq.heapify(tinput) res = [] for i in range (k): t = heapq.heappop(tinput) res.append(t) return res
求前k个最大的数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution : def getMaxNumbers_Solution (self,tinput,k ): ''' 获取前k个大的数 ''' import heapq neg_tinput = [-1 *t for t in tinput] print (neg_tinput) heapq.heapify(neg_tinput) res = [] for i in range (k): t = heapq.heappop(neg_tinput) res.append(t*-1 ) return res
描述 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例：
1 2 3 4 5 输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4
解法：堆排序 python默认是小顶堆，需要调整一下
1 2 3 4 5 6 7 8 9 class Solution : def findKthLargest (self, nums: List [int ], k: int ) -> int : import heapq nums = [-1 *t for t in nums] heapq.heapify(nums) res = 0 for _ in range (k): res = heapq.heappop(nums) return -1 *res
描述 给一非空的单词列表，返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。
解法：重写Python比较方法
参考评论区
