剑指offer：Python 最小的k个数 多种方法实现 最大堆和最小堆

题目描述

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4

思路及Python实现

• 这道题，咋一眼看，可以用很多种排序方式来完成，但是这不单独是为了考察排序；而是在数据量非常大时，什么排序最好，假如输入的数字有上亿个，那么按照十大排序来看，很多排序方式最差时间复杂度都为O（n^2），显然不适合，这样仅剩下“快速排序”和“归并排序”，以及最佳解决方案的“堆排序”来实现！

思路一：快速排序 和 归并排序

快速排序

class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        if len(tinput) < k:
            return []
        return self.quick_sort(tinput)[:k]

    def quick_sort(self, list):
        if len(list) < 2:
            return list[:]
        left = (self.quick_sort([i for i in list[1:] if i <= list[0]]))
        right = (self.quick_sort([i for i in list[1:] if i > list[0]]))
        return left + [list[0]] + right

归并排序

class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        if len(tinput) < k:
            return []
        return self.merge_sort(tinput)[:k]

    def merge_sort(self, list):
        if len(list) < 2:
            return list[:]
        left = self.merge_sort(list[:len(list) // 2])
        right = self.merge_sort(list[len(list) // 2:])
        return self.merge(left, right)

    def merge(self, left, right):
        res = []
        while left and right:
            res.append(left.pop(0)) if left[0] < right[0] else res.append(right.pop(0))
        res += left if not right else right
        return res

思路二：堆 实现

• 堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。
• 分为两种方法：
  大顶堆（最大堆）：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
  小顶堆（最小堆）：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
  堆排序的平均时间复杂度为 Ο(nlogn)
  
  

不用模块，非递归，实现一个最大堆

• 构建最大堆的一些技巧和注意点：
  （1）添加元素时，先从底部往上添加；
  （2）如何通过 根结点 找左右子结点的索引：假设 根结点索引为 index，那么左子结点索引为， index2+1，右子结点为：index2+2，如果 左右子结点索引大于数组长度，则表示该结点的左右子结点不存在（如上图中的“2结点”，22+1 或 22+2 > 4 ）
  （3）如何通过 左右子结点 找出所对应的根结点索引：假设左右子结点的某一个为：index 那么根结点为：（index-1）// 2

class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # 创建或者是插入最大堆
        def creat_max_heap(num):
            max_heap.append(num)
            cur_index = len(max_heap) - 1
            while cur_index != 0:
                parent_index = (cur_index - 1) >> 1
                if max_heap[parent_index] < max_heap[cur_index]:
                    max_heap[parent_index], max_heap[cur_index] = max_heap[cur_index], max_heap[parent_index]
                else:
                    break

        # 调整最大堆，头结点发生改变
        def adjust_max_heap(num):
            if num < max_heap[0]: # 要插入的值 比堆顶的值小，表示可以插入
                max_heap[0] = num
            max_heap_len = len(max_heap) # 计算下最多个数，索引取不到最后一个
            index = 0
            while index < max_heap_len:
                left_index = index * 2 + 1
                right_index = index * 2 + 2
                larger_index = 0 # 找出左右子结点更大的一个，才能和插入的元素互换
                if right_index < max_heap_len:
                    if max_heap[right_index] < max_heap[left_index]:
                        larger_index = left_index
                    else:
                        larger_index = right_index
                elif left_index < max_heap_len:
                    larger_index = left_index
                else:
                    break
                if max_heap[index] < max_heap[larger_index]:
                    max_heap[index], max_heap[larger_index] = max_heap[larger_index], max_heap[index]
                index = larger_index # 更换到某位置，记得将自己身的索引更新

        max_heap = []
        input_len = len(tinput)
        if input_len < k or k <= 0:
            return []
        for i in range(input_len):
            if i < k: # 前 k 个数 先构建一个最大堆
                creat_max_heap(tinput[i])
            else: # 后面的数 来判断调整
                adjust_max_heap(tinput[i])
        max_heap.sort()
        return max_heap

用模块来创建堆，最大堆的 解法

• 用Python中的heapq模块用来建立“堆”的数据结构。
  heapq.heappush(res, -i) 意为：向堆 res 中添加一个元素 -i
  heapq.heappushpop(res, -i)意为：将元素 -i 与堆顶的元素比较。如果该元素值大于堆顶元素，则将该元素与堆顶元素替换。否则不改变堆元素。

import heapq  # 利用heapq模块，来实现堆的操作
class Solution:
	def GetLeastNumbers_Solution(self, tinput, k):
	    if len(tinput) < k:
	        return []
	    res = []
	    for i in tinput:
	        heapq.heappush(res, -i) if len(res) < k else heapq.heappushpop(res, -i)
	    return sorted(list(map(lambda x: -x, res)))

用模块来创建堆

• heapq.nlargest(n, iterable, key=None) 返回最大的n个元素（Top-K问题）

• heapq.nsmallest(n, iterable, key=None) 返回最小的n个元素（Top-K问题）

import heapq  # 利用heapq模块，来实现堆的操作
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        if len(tinput) < k:
            return []
        return heapq.nsmallest(k, tinput)