python 大顶堆

大顶堆（Max Heap）是一种特殊的二叉堆，其中每个节点的值都大于或等于其子节点的值。在Python中，可以使用heapq模块来实现大顶堆。下面是一个示例代码：

import heapq

def build_max_heap(nums):
    heap = []
    for num in nums:
        heapq.heappush(heap, -num)
    return heap

def insert(heap, num):
    heapq.heappush(heap, -num)

def extract_max(heap):
    return -heapq.heappop(heap)

# 示例用法
nums = [4, 1, 7, 3, 8, 5]
max_heap = build_max_heap(nums)
print(extract_max(max_heap))  # 输出：8
insert(max_heap, 10)
print(extract_max(max_heap))  # 输出：10

相关问题

25386147 构建个大顶堆

构建大顶堆的步骤如下：

1. 从最后一个非叶子节点开始，依次向上调整每个节点，使其满足大顶堆的性质。最后一个非叶子节点的索引为 n/2-1，其中 n 是堆的大小。

2. 对于每个非叶子节点 i，比较其与左右子节点的大小，将最大的值作为父节点，并将该值与子节点交换位置。如果发生了交换，则需要递归调整子节点的位置，直到满足大顶堆的性质。

下面是一个示例代码来构建一个大顶堆：

def heapify(arr, n, i):
    # 找到左右子节点的索引
    left = 2 * i + 1
    right = 2 * i + 2
    largest = i

    # 找到最大值
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right

    # 如果最大值不是父节点，则交换位置，并递归调整子节点的位置
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def build_heap(arr):
    n = len(arr)

    # 从最后一个非叶子节点开始，依次向上调整每个节点
    for i in range(n//2-1, -1, -1):
        heapify(arr, n, i)

    return arr

你可以使用以下代码来测试：

arr = [4, 10, 3, 5, 1]
print(build_heap(arr))  # 输出 [10, 5, 3, 4, 1]

priorityqueue小顶堆

PriorityQueue是Java中的一个数据结构，它可以实现优先级队列。默认情况下，PriorityQueue是以小顶堆的形式实现的，也就是说，优先级最小的元素位于队列的头部。

在Python中，PriorityQueue也是以小顶堆的形式实现的。如果你想要实现一个大顶堆的PriorityQueue，可以通过将元素的优先级取相反数来实现。具体的做法是，在将元素插入队列之前，将它的优先级取负数，这样优先级高的元素就会排在队列的前面。

在Java中，你可以通过构造PriorityQueue时传入一个Comparator来实现大顶堆。Comparator是一个比较器，它定义了元素之间的比较规则。如果你想要实现一个大顶堆，可以创建一个Comparator，将o1和o2进行比较，并返回o2 - o1的结果。这样，优先级高的元素会排在队列的前面。

综上所述，PriorityQueue默认是小顶堆，如果你想要实现大顶堆，可以通过将元素的优先级取相反数来实现（在Python中），或者通过传入一个Comparator来实现（在Java中）。

引用自：https://docs.oracle.com/en/java/javase/16/docs/api/java.base/java/util/PriorityQueue.html
引用自：https://docs.python.org/3/library/heapq.html
引用自：https://www.geeksforgeeks.org/priority-queue-class-in-java-2/