LeetCode刷题 堆

一：堆

1、一种二叉树的结构（完全二叉树）

2、完全二叉树：从上到下；从左到右；填满

3、最大堆：根节点的权值大于孩子节点

4、最小堆：根节点的权值依次小于孩子节点

5、常用操作

#创建堆（最大堆，最小堆）
#添加元素
#获取堆顶元素
#删除堆顶元素
#堆的长度
#堆的遍历

二：刷题

215 数组中的第K个最大元素

#方法1 数组
def func(nums,k):
    nums.sort()
    return nums[-k]
nums=[3,2,3,1,2,4,5,5,6]
k = 4
print(func(nums,k))
#方法2 最大堆
import heapq

def func(nums, k):
    # Step 1: 取数组的前 k 个元素，构建最小堆
    min_heap = nums[:k]
    heapq.heapify(min_heap)  # 将列表转换为最小堆

    # Step 2: 遍历剩余的元素
    for num in nums[k:]:
        if num > min_heap[0]:  # 如果当前元素大于堆顶元素
            heapq.heappop(min_heap)  # 移除堆顶元素
            heapq.heappush(min_heap, num)  # 将当前元素加入堆

    # Step 3: 返回堆顶元素
    return min_heap[0]