笙亿网络策划

DSA 堆数据结构怎么用？Heap 实现和操作详解？

约 39 分钟读完 35 阅
文章导读
上一个 测验 下一个 堆是一种特殊的平衡二叉树数据结构，其中根节点的关键值与其子节点进行比较并相应排列。如果 α 有子节点 β，则 −
📋 目录
  1. 一 最大堆构建算法
  2. 二 最大堆删除算法
A A

堆数据结构

目录
  • 最大堆构建算法
  • 最大堆删除算法
上一个
测验
下一个

堆是一种特殊的平衡二叉树数据结构，其中根节点的关键值与其子节点进行比较并相应排列。如果 α 有子节点 β，则 −

key(α) ≥ key(β)

由于父节点的值大于子节点的值，此属性生成 Max Heap。基于此标准，堆可以分为两种类型 −

For Input → 35 33 42 10 14 19 27 44 26 31

Min-Heap − 根节点的值小于或等于其任一子节点的值。

Max Heap Example

Max-Heap − 根节点的值大于或等于其任一子节点的值。

Max Heap Example

两棵树使用相同的输入和到达顺序构建。

最大堆构建算法

我们将使用相同的示例来演示如何创建 Max Heap。创建 Min Heap 的过程类似，但我们选择最小值而不是最大值。

我们将通过逐个插入元素来推导最大堆的算法。在任何时候，heap 都必须保持其性质。在插入过程中，我们假设我们正在向一个已经 heapified 的树中插入一个节点。

步骤 1 − 在 heap 的末尾创建一个新节点。
步骤 2 − 为新节点赋值。
步骤 3 − 将此子节点的值与其父节点进行比较。
步骤 4 − 如果父节点的值小于子节点，则交换它们。
步骤 5 − 重复步骤 3 和 4，直到 Heap 属性成立。

注意 − 在 Min Heap 构建算法中，我们期望父节点的值小于子节点的值。

让我们通过动画图示来理解 Max Heap 的构建。我们考虑之前使用的相同输入样本。

Max Heap Animated Example

示例

以下是此操作在各种编程语言中的实现 −

C C++ Java Python 
//C code for Max Heap construction  Algorithm
#include <stdio.h>
#include <stdlib.h>
// 用于表示 heap 的结构
typedef struct {
    int* array;     // 用于存储 heap 元素的数组
    int capacity;   // heap 的最大容量
    int size;       // heap 当前大小
} Heap;
// 创建一个新 heap 的函数
Heap* createHeap(int capacity)
{
    Heap* heap = (Heap*)malloc(sizeof(Heap));
    heap->array = (int*)malloc(capacity * sizeof(int));
    heap->capacity = capacity;
    heap->size = 0;
    return heap;
}
// 在 heap 中交换两个元素的函数
void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
// 对以索引 i 为根的子树进行 heapify 的函数
void heapify(Heap* heap, int i)
{
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    // 检查左子节点是否大于根节点
    if (left < heap->size && heap->array[left] > heap->array[largest])
        largest = left;
    // 检查右子节点是否大于目前最大的节点
    if (right < heap->size && heap->array[right] > heap->array[largest])
        largest = right;
    // 如果最大值不是根节点，则将根节点与最大值交换
    if (largest != i) {
        swap(&heap->array[i], &heap->array[largest]);
        heapify(heap, largest);
    }
}
// 将新元素插入 heap 的函数
void insert(Heap* heap, int value)
{
    if (heap->size == heap->capacity) {
        printf("Heap is full. Cannot insert more elements.\n");
        return;
    }
    // 在末尾插入新元素
    int i = heap->size++;
    heap->array[i] = value;
    // 如果违反了 heap 属性，则修复它
    while (i != 0 && heap->array[(i - 1) / 2] < heap->array[i]) {
        swap(&heap->array[i], &heap->array[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}
// 从 heap 中提取最大元素的函数
int extractMax(Heap* heap)
{
    if (heap->size == 0) {
        printf("Heap is empty. Cannot extract maximum element.\n");
        return -1;
    }
    // 存储根元素
    int max = heap->array[0];
    // 用最后一个元素替换根节点
    heap->array[0] = heap->array[heap->size - 1];
    heap->size--;
    // 对根节点进行 heapify
    heapify(heap, 0);
    return max;
}
// 打印 heap 元素的函数
void printHeap(Heap* heap)
{
    printf("Heap elements: ");
    for (int i = 0; i < heap->size; i++) {
        printf("%d ", heap->array[i]);
    }
    printf("\n");
}
// heap 的示例用法
int main()
{
    Heap* heap = createHeap(10);
    insert(heap, 35);
    insert(heap, 33);
    insert(heap, 42);
    insert(heap, 10);
    insert(heap, 14);
    insert(heap, 19);
    insert(heap, 27);
    insert(heap, 44);
    insert(heap, 26);
    insert(heap, 31);
    printHeap(heap);
    int max = extractMax(heap);
    printf("Maximum element: %d\n", max);
    return 0;
}

输出

Heap elements: 44 42 35 33 31 19 27 10 26 14 
Maximum element: 44

//C++ code for Max Heap construction  Algorithm
#include <iostream>
// 用于表示 heap 的结构
struct Heap {
    int* array;     // 用于存储 heap 元素的数组
    int capacity;   // heap 的最大容量
    int size;       // heap 当前大小
};
// 创建一个新 heap 的函数
Heap* createHeap(int capacity)
{
    Heap* heap = new Heap;
    heap->array = new int[capacity];
    heap->capacity = capacity;
    heap->size = 0;
    return heap;
}
// 在 heap 中交换两个元素的函数
void swap(int& a, int& b)
{
    int temp = a;
    a = b;
    b = temp;
}
// 对以索引 i 为根的子树进行 heapify 的函数
void heapify(Heap* heap, int i)
{
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    // 检查左子节点是否大于根节点
    if (left <heap->size && heap->array[left] > heap->array[largest])
        largest = left;
    // 检查右子节点是否大于目前最大的节点
    if (right <heap->size && heap->array[right] > heap->array[largest])
        largest = right;
    // 如果最大值不是根节点，则将根节点与最大值交换
    if (largest != i) {
        swap(heap->array[i], heap->array[largest]);
        heapify(heap, largest);
    }
}
// 将新元素插入 heap 的函数
void insert(Heap* heap, int value)
{
    if (heap->size == heap->capacity) {
        std::cout << "Heap is full. Cannot insert more elements." << std::endl;
        return;
    }
    // 在末尾插入新元素
    int i = heap->size++;
    heap->array[i] = value;
    // 如果违反了 heap 属性，则修复它
    while (i != 0 && heap->array[(i - 1) / 2] < heap->array[i]) {
        swap(heap->array[i], heap->array[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}
// 从 heap 中提取最大元素的函数
int extractMax(Heap* heap)
{
    if (heap->size == 0) {
        std::cout << "Heap is empty. Cannot extract maximum element." << std::endl;
        return -1;
    }
    // 存储根元素
    int max = heap->array[0];
    // 用最后一个元素替换根节点
    heap->array[0] = heap->array[heap->size - 1];
    heap->size--;
    // 对根节点进行 heapify
    heapify(heap, 0);
    return max;
}
// 打印 heap 元素的函数
void printHeap(Heap* heap)
{
    std::cout << "Heap elements: ";
    for (int i = 0; i < heap->size; i++) {
        std::cout << heap->array[i] << " ";
    }
    std::cout << std::endl;
}
// heap 的示例用法
int main()
{
    Heap* heap = createHeap(10);
    insert(heap, 35);
    insert(heap, 33);
    insert(heap, 42);
    insert(heap, 10);
    insert(heap, 14);
    insert(heap, 19);
    insert(heap, 27);
    insert(heap, 44);
    insert(heap, 26);
    insert(heap, 31);

    printHeap(heap);

    int max = extractMax(heap);
    std::cout << "Maximum element: " << max << std::endl;

    return 0;
}

输出

Heap elements: 44 42 35 33 31 19 27 10 26 14 
Maximum element: 44

// Java code for for Max Heap construction  Algorithm
//用于表示 heap 的结构
public class MaxHeap {
    private int[] heap; // 用于存储 heap 元素的数组
    private int capacity; // heap 的最大容量
    private int size; // heap 当前大小
    // 创建一个新 heap
    public MaxHeap(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.heap = new int[capacity];
    }
    private int parent(int i) {
        return (i - 1) / 2;
    }
    private int leftChild(int i) {
        return 2 * i + 1;
    }
    private int rightChild(int i) {
        return 2 * i + 2;
    }
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
   // 对以索引 i 为根的子树进行 heapify
    private void heapifyDown(int i) {
        int largest = i;
        int left = leftChild(i);
        int right = rightChild(i);     
        // 检查左子节点是否大于根节点
        if (left < size && heap[left] > heap[largest])
            largest = left;         
        // 检查右子节点是否大于目前最大的节点
        if (right < size && heap[right] > heap[largest])
            largest = right;
        // 如果最大值不是根节点，则将根节点与最大值交换
        if (largest != i) {
            swap(i, largest);
            heapifyDown(largest);
        }
    }
    private void heapifyUp(int i) {
        while (i > 0 && heap[i] > heap[parent(i)]) {
            int parent = parent(i);
            swap(i, parent);
            i = parent;
        }
    }
    // 在末尾插入新元素
    public void insert(int value) {
        if (size == capacity) {
            System.out.println("Heap is full. Cannot insert more elements.");
            return;
        }
        heap[size] = value;
        size++;
        heapifyUp(size - 1);
    }
    // 从 heap 中提取最大元素的函数
    public int extractMax() {
        if (size == 0) {
            System.out.println("Heap is empty. Cannot extract maximum element.");
            return -1;
        }
        // 存储根元素
        int max = heap[0];
        //用最后一个元素替换根节点
        heap[0] = heap[size - 1];
        size--;
        heapifyDown(0);
        return max;
    } 
    //打印 heap 的元素
    public void printHeap() {
        System.out.print("Heap elements: ");
        for (int i = 0; i < size; i++) {
            System.out.print(heap[i] + " ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        MaxHeap heap = new MaxHeap(10);
        heap.insert(35);
        heap.insert(33);
        heap.insert(42);
        heap.insert(10);
        heap.insert(14);
        heap.insert(19);
        heap.insert(27);
        heap.insert(44);
        heap.insert(26);
        heap.insert(31);
        heap.printHeap();
        int max = heap.extractMax();
        System.out.println("Maximum element: " + max);
    }
}

输出

Heap elements: 44 42 35 33 31 19 27 10 26 14 
Maximum element: 44

# Python code for for Max Heap construction  Algorithm
class MaxHeap:
    def __init__(self):
        self.heap = []
    def parent(self, i):
        return (i - 1) // 2
    def left_child(self, i):
        return 2 * i + 1
    def right_child(self, i):
        return 2 * i + 2
    #在 heap 中交换两个元素的函数
    def swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
    # 对以索引 i 为根的子树进行 heapify 的函数
    def heapify_down(self, i):
        left = self.left_child(i)
        right = self.right_child(i)
        largest = i
        #检查左子节点是否大于根节点
        if left < len(self.heap) and self.heap[left] >self.heap[largest]:
            largest = left
        # 检查右子节点是否大于目前最大的节点
        if right < len(self.heap) and self.heap[right] > self.heap[largest]:
            largest = right

        # 如果最大值不是根节点，则将根节点与最大值交换
        if largest != i:
            self.swap(i, largest)
            self.heapify_down(largest)
    def heapify_up(self, i):
        while i > 0 and self.heap[i] > self.heap[self.parent(i)]:
            parent = self.parent(i)
            self.swap(i, parent)
            i = parent
    # 在末尾插入新元素
    def insert(self, value):
        self.heap.append(value)
        # 如果违反了 heap 属性，则修复它
        self.heapify_up(len(self.heap) - 1)
    # 从 heap 中提取最大元素的函数
    def extract_max(self):
        if len(self.heap) == 0:
            print("Heap is empty. Cannot extract maximum element.")
            return None
        max_value = self.heap[0]
        self.heap[0] = self.heap[-1]
        self.heap.pop()
        self.heapify_down(0)
        return max_value
    # 打印 heap 元素的函数
    def print_heap(self):
        print("Heap elements:", end=" ")
        for value in self.heap:
            print(value, end=" ")
        print()
# heap 的示例用法
heap = MaxHeap()
heap.insert(35)
heap.insert(33)
heap.insert(42)
heap.insert(10)
heap.insert(14)
heap.insert(19)
heap.insert(27)
heap.insert(44)
heap.insert(26)
heap.insert(31)
heap.print_heap()
max_value = heap.extract_max()
print("Maximum element:", max_value)

输出

Heap elements: 44 42 35 33 31 19 27 10 26 14 
Maximum element: 44s

最大堆删除算法

让我们推导一个从最大堆中删除元素的算法。在 Max（或 Min）Heap 中，删除总是发生在根节点，以移除最大（或最小）值。

步骤 1 − 删除根节点。
步骤 2 − 将最后一层的最后一个元素移动到根节点。
步骤 3 − 将此子节点的值与其父节点进行比较。
步骤 4 − 如果父节点的值小于子节点，则交换它们。
步骤 5 − 重复步骤 3 和 4，直到满足 Heap 属性。
Max Heap Deletion Animated Example

示例

以下是此操作在各种编程语言中的实现 −

C C++ Java Python 
//C 最大堆删除算法代码
#include <stdio.h>
#include <stdlib.h>
// 表示堆的结构
typedef struct {
    int* array;     // 存储堆元素的数组
    int capacity;   // 堆的最大容量
    int size;       // 堆的当前大小
} Heap;
// 创建一个新的堆
Heap* createHeap(int capacity)
{
    Heap* heap = (Heap*)malloc(sizeof(Heap));
    heap->array = (int*)malloc(capacity * sizeof(int));
    heap->capacity = capacity;
    heap->size = 0;
    return heap;
}
// 在堆中交换两个元素
void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
// 对以索引 i 为根的子树进行 heapify
void heapify(Heap* heap, int i)
{
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    // 检查左子节点是否大于根节点
    if (left < heap->size && heap->array[left] > heap->array[largest])
        largest = left;
    // 检查右子节点是否大于目前最大的节点
    if (right < heap->size && heap->array[right] > heap->array[largest])
        largest = right;
    // 如果最大值不是根节点，则将根节点与最大值交换
    if (largest != i) {
        swap(&heap->array[i], &heap->array[largest]);
        heapify(heap, largest);
    }
}
// 将新元素插入堆中
void insert(Heap* heap, int value)
{
    if (heap->size == heap->capacity) {
        printf("堆已满。无法插入更多元素。\n");
        return;
    }
    // 将新元素插入到末尾
    int i = heap->size++;
    heap->array[i] = value;
    // 如果违反了堆属性，则修复堆属性
    while (i != 0 && heap->array[(i - 1) / 2] < heap->array[i]) {
        swap(&heap->array[i], &heap->array[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}
// 从堆中删除最大元素
int deleteMax(Heap* heap)
{
    if (heap->size == 0) {
        printf("堆为空。无法提取最大元素。\n");
        return -1;
    }
    // 存储根元素
    int max = heap->array[0];
    // 用最后一个元素替换根节点
    heap->array[0] = heap->array[heap->size - 1];
    heap->size--;
    // 对根节点进行 heapify
    heapify(heap, 0);
    return max;
}
// 打印堆中的元素
void printHeap(Heap* heap)
{
    for (int i = 0; i < heap->size; i++) {
        printf("%d ", heap->array[i]);
    }
    printf("\n");
}
// 释放堆占用的内存
void destroyHeap(Heap* heap)
{
    free(heap->array);
    free(heap);
}
// 堆的使用示例
int main()
{
    Heap* heap = createHeap(10);
    insert(heap, 35);
    insert(heap, 33);
    insert(heap, 42);
    insert(heap, 10);
    insert(heap, 14);
    insert(heap, 19);
    insert(heap, 27);
    insert(heap, 44);
    insert(heap, 26);
    insert(heap, 31);
	printf("删除前的堆元素: ");
    printHeap(heap);
    // 删除堆中的最大元素
    int max = deleteMax(heap);
    printf("最大元素: %d\n", max);
	printf("删除后的堆元素: ");
    printHeap(heap);
    destroyHeap(heap);
    return 0;
}

输出

删除前的堆元素: 44 42 35 33 31 19 27 10 26 14 
最大元素: 44
删除后的堆元素: 42 33 35 26 31 19 27 10 14

//C++ 最大堆删除算法代码
#include <iostream>
// 表示堆的结构
struct Heap {
    int* array;     // 存储堆元素的数组
    int capacity;   // 堆的最大容量
    int size;       // 堆的当前大小
};
// 创建一个新的堆
Heap* createHeap(int capacity)
{
    Heap* heap = new Heap;
    heap->array = new int[capacity];
    heap->capacity = capacity;
    heap->size = 0;
    return heap;
}
// 在堆中交换两个元素
void swap(int& a, int& b)
{
    int temp = a;
    a = b;
    b = temp;
}
// 对以索引 i 为根的子树进行 heapify
void heapify(Heap* heap, int i)
{
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    // 检查左子节点是否大于根节点
    if (left < heap->size && heap->array[left] > heap->array[largest])
        largest = left;
    // 检查右子节点是否大于目前最大的节点
    if (right < heap->size && heap->array[right] > heap->array[largest])
        largest = right;
    // 如果最大值不是根节点，则将根节点与最大值交换
    if (largest != i) {
        swap(heap->array[i], heap->array[largest]);
        heapify(heap, largest);
    }
}
// 将新元素插入堆中
void insert(Heap* heap, int value)
{
    if (heap->size == heap->capacity) {
        std::cout << "堆已满。无法插入更多元素。" << std::endl;
        return;
    }
    // 将新元素插入到末尾
    int i = heap->size++;
    heap->array[i] = value;

    // 如果违反了堆属性，则修复堆属性
    while (i != 0 && heap->array[(i - 1) / 2] < heap->array[i]) {
        swap(heap->array[i], heap->array[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}
// 从堆中删除最大元素
int deleteMax(Heap* heap)
{
    if (heap->size == 0) {
        std::cout << "堆为空。无法提取最大元素。" << std::endl;
        return -1;
    }
    // 存储根元素
    int max = heap->array[0];
    // 用最后一个元素替换根节点
    heap->array[0] = heap->array[heap->size - 1];
    heap->size--;
    // 对根节点进行 heapify
    heapify(heap, 0);

    return max;
}
// 打印堆中的元素
void printHeap(Heap* heap)
{
    for (int i = 0; i < heap->size; i++) {
        std::cout << heap->array[i] << " ";
    }
    std::cout << std::endl;
}
// 释放堆占用的内存
void destroyHeap(Heap* heap)
{
    delete[] heap->array;
    delete heap;
}
// 堆的使用示例
int main()
{
    Heap* heap = createHeap(10);
    insert(heap, 35);
    insert(heap, 33);
    insert(heap, 42);
    insert(heap, 10);
    insert(heap, 14);
    insert(heap, 19);
    insert(heap, 27);
    insert(heap, 44);
    insert(heap, 26);
    insert(heap, 31);
	std::cout << "删除前的堆元素: ";
    printHeap(heap);
    int max = deleteMax(heap);
    std::cout << "最大元素: " << max << std::endl;
	std::cout << "删除后的堆元素: ";
    printHeap(heap);
    destroyHeap(heap);
    return 0;
}

输出

删除前的堆元素: 44 42 35 33 31 19 27 10 26 14 
最大元素: 44
删除后的堆元素: 42 33 35 26 31 19 27 10 14 

// Java 最大堆删除算法代码
// 表示堆的结构
class Heap {
    private int[] array;  // 存储堆元素的数组
    private int capacity;  // 堆的最大容量
    private int size;      // 堆的当前大小
    // 创建一个新的堆
    public Heap(int capacity) {
        this.array = new int[capacity];
        this.capacity = capacity;
        this.size = 0;
    }
    // 在堆中交换两个元素
    private void swap(int a, int b) {
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
    // 对以索引 i 为根的子树进行 heapify
    private void heapify(int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;     
        // 检查左子节点是否大于根节点
        if (left < size && array[left] > array[largest])
            largest = left;         
        // 检查右子节点是否大于目前最大的节点
        if (right < size && array[right] > array[largest])
            largest = right;
        // 如果最大值不是根节点，则将根节点与最大值交换
        if (largest != i) {
            swap(i, largest);
            heapify(largest);
        }
    }
    // 将新元素插入堆中
    public void insert(int value) {
        if (size == capacity) {
            System.out.println("堆已满。无法插入更多元素。");
            return;
        }
        // 将新元素插入到末尾
        int i = size++;
        array[i] = value;
        // 如果违反了堆属性，则修复堆属性
        while (i != 0 && array[(i - 1) / 2] < array[i]) {
            swap(i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }
    // 从堆中删除最大元素
    public int deleteMax() {
        if (size == 0) {
            System.out.println("堆为空。无法提取最大元素。");
            return -1;
        }
        // 存储根元素
        int max = array[0];
        // 用最后一个元素替换根节点
        array[0] = array[size - 1];
        size--;
        // 对根节点进行 heapify
        heapify(0);
        return max;
    }
    // 打印堆中的元素
    public void printHeap() {
        for (int i = 0; i < size; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
    // 释放堆占用的内存
    public void destroyHeap() {
        array = null;
        size = 0;
    }
}
//插入元素
public class Main {
    public static void main(String[] args) {
        Heap heap = new Heap(10);
        heap.insert(35);
        heap.insert(33);
        heap.insert(42);
        heap.insert(10);
        heap.insert(14);
        heap.insert(19);
        heap.insert(27);
        heap.insert(44);
        heap.insert(26);
        heap.insert(31);
		System.out.print("删除前的堆元素: ");
        heap.printHeap();
        int max = heap.deleteMax();
        System.out.println("最大元素: " + max);  
        //打印删除最大元素后的堆元素
		System.out.print("删除后的堆元素: ");
        heap.printHeap();
        heap.destroyHeap();
    }
}

输出

删除前的堆元素: 44 42 35 33 31 19 27 10 26 14 
最大元素: 44
删除后的堆元素: 42 33 35 26 31 19 27 10 14 

#Python 最大堆删除算法代码
class Heap:
    def __init__(self, capacity):
        self.array = [0] * capacity  #存储堆元素的数组
        self.capacity = capacity  #堆的最大容量
        self.size = 0  #堆的当前大小
    # 在堆中交换两个元素
    def swap(self, a, b):
        self.array[a], self.array[b] = self.array[b], self.array[a]
    # 对以索引 i 为根的子树进行 heapify
    def heapify(self, i):
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2
        # 检查左子节点是否大于根节点
        if left < self.size and self.array[left] > self.array[largest]:
            largest = left
        # 检查右子节点是否大于目前最大的节点
        if right < self.size and self.array[right] > self.array[largest]:
            largest = right
        # 如果最大值不是根节点，则将根节点与最大值交换
        if largest != i:
            self.swap(i, largest)
            self.heapify(largest)
    # 将新元素插入堆中
    def insert(self, value):
        if self.size == self.capacity:
            print("堆已满。无法插入更多元素。")
            return
        # 将新元素插入到末尾
        i = self.size
        self.size += 1
        self.array[i] = value
        # 如果违反了堆属性，则修复堆属性
        while i != 0 and self.array[(i - 1) // 2] < self.array[i]:
            self.swap(i, (i - 1) // 2)
            i = (i - 1) // 2
    # 从堆中删除最大元素
    def deleteMax(self):
        if self.size == 0:
            print("堆为空。无法提取最大元素。")
            return -1
        # 存储根元素
        max_value = self.array[0]
        # 用最后一个元素替换根节点
        self.array[0] = self.array[self.size - 1]
        self.size -= 1
        # 对根节点进行 heapify
        self.heapify(0)
        return max_value
    # 打印堆中的元素
    def printHeap(self):
        for i in range(self.size):
            print(self.array[i], end=" ")
        print()
    # 释放堆占用的内存
    def destroyHeap(self):
        self.array = []
        self.size = 0
# 堆的使用示例
heap = Heap(10)
heap.insert(35)
heap.insert(33)
heap.insert(42)
heap.insert(10)
heap.insert(14)
heap.insert(19)
heap.insert(27)
heap.insert(44)
heap.insert(26)
heap.insert(31)
print("删除前的堆元素:", end=" ")
heap.printHeap()
max_value = heap.deleteMax()
print("最大元素:", max_value)
print("删除后的堆元素:", end=" ")
heap.printHeap()
heap.destroyHeap()

输出

删除前的堆元素: 44 42 35 33 31 19 27 10 26 14 
最大元素: 44
删除后的堆元素: 42 33 35 26 31 19 27 10 14