牛客网---堆（python实现）

客官°小女子只卖身不卖艺 2022-10-23 14:30 171阅读 0赞

### 堆是个什么玩意？能难住我？ ###

*   *   *  0：堆与堆排序：
         *  一：最小的K个数：
         *  二：寻找第K大：

### 0：堆与堆排序： ###

# 构建大根堆：
    def heapify(arr, n, i):
        largest = i
        l = 2 * i + 1  # left = 2*i + 1
        r = 2 * i + 2  # right = 2*i + 2
    
        if l < n and arr[i] < arr[l]: # 根节点小于左节点
            largest = l # 左节点是最大结点
    
        if r < n and arr[largest] < arr[r]: # 右节点大于最大结点，则右节点是最大结点
            largest = r
    
        if largest != i: # 如果最大结点不是根节点
            arr[i], arr[largest] = arr[largest], arr[i]  # 交换根节点和最大结点
            heapify(arr, n, largest) # 调换完了，我看看换完了之后是不是还是大根堆。
    
    
    def heapSort(arr):
        n = len(arr) # 堆长度
        for i in range(n - 1, -1, -1): # 从后向前递归创建大根堆
            heapify(arr, n, i)
        for i in range(n - 1, 0, -1):
            arr[i], arr[0] = arr[0], arr[i]  # 交换
            heapify(arr, i, 0) # 调整大根堆

### 一：最小的K个数： ###

给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。如果K>数组的长度，那么返回一个空的数组

class Solution:
        # 构建大根堆：
        def heapify(self,arr, n, i):
            largest = i
            l = 2 * i + 1  # left = 2*i + 1
            r = 2 * i + 2  # right = 2*i + 2
    
            if l < n and arr[i] < arr[l]: # 根节点小于左节点
                largest = l # 左节点是最大结点
    
            if r < n and arr[largest] < arr[r]: # 右节点大于最大结点，则右节点是最大结点
                largest = r
    
            if largest != i: # 如果最大结点不是根节点
                arr[i], arr[largest] = arr[largest], arr[i]  # 交换根节点和最大结点
                self.heapify(arr, n, largest) # 调换完了，我看看换完了之后是不是还是大根堆。
    
    
        def heapSort(self,arr):
            n = len(arr) # 堆长度
            for i in range(n - 1, -1, -1): # 从后向前递归创建大根堆
                self.heapify(arr, n, i)
            for i in range(n - 1, 0, -1):
                arr[i], arr[0] = arr[0], arr[i]  # 交换
                self.heapify(arr, i, 0) # 调整大根堆
            
        def GetLeastNumbers_Solution(self, tinput, k):
            length = len(tinput)
            if k > length:
                return []
            else:
                self.heapSort(tinput)
                return tinput[:k]

### 二：寻找第K大： ###

有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。  
给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存在。

class Solution:
            # 构建大根堆：
        def heapify(self,arr, n, i):
            largest = i
            l = 2 * i + 1  # left = 2*i + 1
            r = 2 * i + 2  # right = 2*i + 2
    
            if l < n and arr[i] < arr[l]: # 根节点小于左节点
                largest = l # 左节点是最大结点
    
            if r < n and arr[largest] < arr[r]: # 右节点大于最大结点，则右节点是最大结点
                largest = r
    
            if largest != i: # 如果最大结点不是根节点
                arr[i], arr[largest] = arr[largest], arr[i]  # 交换根节点和最大结点
                self.heapify(arr, n, largest) # 调换完了，我看看换完了之后是不是还是大根堆。
    
    
        def heapSort(self,arr):
            n = len(arr) # 堆长度
            for i in range(n - 1, -1, -1): # 从后向前递归创建大根堆
                self.heapify(arr, n, i)
            for i in range(n - 1, 0, -1):
                arr[i], arr[0] = arr[0], arr[i]  # 交换
                self.heapify(arr, i, 0) # 调整大根堆
            
        def findKth(self, a, n, K):
            if n < K:
                return []
            self.heapSort(a)
            return a[n-K]