数据结构第17节最小堆

🕗 发布于 2024-07-13 21:35 数据结构 python 算法 java java-ee

最小堆（Min Heap）是一种特殊的完全二叉树数据结构，在这种结构中，对于任意节点，其值都小于或等于它的子节点的值。根节点是堆中的最小元素。最小堆常用于实现优先队列，以及堆排序算法。

在Java中，我们可以使用数组或ArrayList来实现最小堆，因为完全二叉树的特性允许我们通过简单的数学运算在数组中找到父节点和子节点的位置。

最小堆的基本操作：

插入元素：将新元素添加到数组的末尾，然后从下至上调整以保持最小堆的性质。
删除最小元素：移除数组的第一个元素（即堆顶），然后将最后一个元素移到堆顶，再从上至下调整以保持堆的性质。
获取最小元素：直接访问数组的第一个元素。

示例代码：

下面是一个简单的Java实现最小堆的示例：

import java.util.Arrays;

public class MinHeap {
    private int[] heap;
    private int size;

    public MinHeap(int capacity) {
        heap = new int[capacity];
        size = 0;
    }

    // 插入元素
    public void insert(int value) {
        if (size == heap.length) {
            throw new IllegalStateException("Heap is full");
        }
        heap[size] = value;
        siftUp(size);
        size++;
    }

    // 上浮操作，保持最小堆性质
    private void siftUp(int index) {
        while (index > 0) {
            int parentIndex = (index - 1) / 2;
            if (heap[parentIndex] > heap[index]) {
                swap(parentIndex, index);
                index = parentIndex;
            } else {
                break;
            }
        }
    }

    // 删除并返回最小元素
    public int extractMin() {
        if (size == 0) {
            throw new IllegalStateException("Heap is empty");
        }
        int min = heap[0];
        heap[0] = heap[size - 1];
        size--;
        siftDown(0);
        return min;
    }

    // 下沉操作，保持最小堆性质
    private void siftDown(int index) {
        int leftChildIndex = 2 * index + 1;
        int rightChildIndex = 2 * index + 2;
        int smallest = index;

        if (leftChildIndex < size && heap[leftChildIndex] < heap[smallest]) {
            smallest = leftChildIndex;
        }
        if (rightChildIndex < size && heap[rightChildIndex] < heap[smallest]) {
            smallest = rightChildIndex;
        }
        if (smallest != index) {
            swap(index, smallest);
            siftDown(smallest);
        }
    }

    // 交换两个元素
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    // 打印堆的内容
    public void printHeap() {
        System.out.println(Arrays.toString(Arrays.copyOf(heap, size)));
    }
}

使用示例：

public class Main {
    public static void main(String[] args) {
        MinHeap heap = new MinHeap(10);
        heap.insert(10);
        heap.insert(1);
        heap.insert(15);
        heap.insert(5);
        heap.printHeap(); // 输出: [1, 5, 10, 15]
        System.out.println("Extracted min: " + heap.extractMin()); // 输出: Extracted min: 1
        heap.printHeap(); // 输出: [5, 10, 15]
    }
}

这段代码创建了一个最小堆，并提供了插入和删除最小元素的功能。注意，实际应用中可能需要处理堆满或空的情况，以及可能的异常情况。此外，上述代码未包含容量自动扩展的逻辑，实际使用时应考虑这一点。

为了使代码更加健壮和实用，我们可以添加以下功能：

自动扩展堆的容量：当插入元素导致堆溢出时，动态地增加堆的大小。
堆的初始化：提供一个构造函数接受一个数组，可以立即构建一个最小堆。
获取堆的大小和是否为空的方法。

以下是完善后的代码：

import java.util.Arrays;

public class MinHeap {
    private int[] heap;
    private int size;
    private int capacity;

    public MinHeap(int capacity) {
        this.capacity = capacity;
        heap = new int[capacity];
        size = 0;
    }

    // 构造函数，接收一个数组，构建最小堆
    public MinHeap(int[] arr) {
        this(arr.length);
        for (int value : arr) {
            insert(value);
        }
    }

    public void insert(int value) {
        ensureCapacity();
        heap[size] = value;
        siftUp(size);
        size++;
    }

    private void ensureCapacity() {
        if (size == heap.length) {
            int newCapacity = heap.length * 2;
            heap = Arrays.copyOf(heap, newCapacity);
            capacity = newCapacity;
        }
    }

    public int extractMin() {
        if (size == 0) {
            throw new IllegalStateException("Heap is empty");
        }
        int min = heap[0];
        heap[0] = heap[size - 1];
        size--;
        siftDown(0);
        return min;
    }

    private void siftUp(int index) {
        while (index > 0) {
            int parentIndex = (index - 1) / 2;
            if (heap[parentIndex] > heap[index]) {
                swap(parentIndex, index);
                index = parentIndex;
            } else {
                break;
            }
        }
    }

    private void siftDown(int index) {
        int leftChildIndex = 2 * index + 1;
        int rightChildIndex = 2 * index + 2;
        int smallest = index;

        if (leftChildIndex < size && heap[leftChildIndex] < heap[smallest]) {
            smallest = leftChildIndex;
        }
        if (rightChildIndex < size && heap[rightChildIndex] < heap[smallest]) {
            smallest = rightChildIndex;
        }
        if (smallest != index) {
            swap(index, smallest);
            siftDown(smallest);
        }
    }

    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    public void printHeap() {
        System.out.println(Arrays.toString(Arrays.copyOf(heap, size)));
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }
}

使用示例：

public class Main {
    public static void main(String[] args) {
        int[] arr = {10, 1, 15, 5};
        MinHeap heap = new MinHeap(arr);

        System.out.println("Initial heap:");
        heap.printHeap();

        System.out.println("\nExtracted min: " + heap.extractMin());
        System.out.println("Heap after extraction:");
        heap.printHeap();

        System.out.println("\nInserting 3:");
        heap.insert(3);
        heap.printHeap();
        
        System.out.println("\nHeap size: " + heap.getSize());
        System.out.println("Is heap empty? " + heap.isEmpty());
    }
}

这个版本的最小堆类现在可以处理动态容量扩展，初始化一个已有元素的堆，以及提供了一些额外的辅助方法。

让我们通过一个表格逐步演示如何使用上面定义的 MinHeap 类。我们将执行一系列操作，包括插入元素、提取最小元素、检查堆的状态等。

初始状态

Index	Value
0	-
1	-
2	-
3	-
4	-
Size	0

操作 1: 插入元素 10

Index	Value
0	10
1	-
2	-
3	-
4	-
Size	1

操作 2: 插入元素 1

Index	Value
0	1
1	10
2	-
3	-
4	-
Size	2

操作 3: 插入元素 15

Index	Value
0	1
1	10
2	15
3	-
4	-
Size	3

操作 4: 插入元素 5

Index	Value
0	1
1	5
2	10
3	15
4	-
Size	4

操作 5: 提取最小元素

提取后，堆中最小元素（1）被删除，最后一个元素（15）被移动到堆顶，并进行下沉操作以保持堆的性质。

Index	Value
0	15
1	5
2	10
3	-
4	-
Size	3

进行下沉操作后：

Index	Value
0	5
1	10
2	15
3	-
4	-
Size	3

操作 6: 插入元素 3

Index	Value
0	3
1	5
2	10
3	15
4	-
Size	4

操作 7: 检查堆的大小和是否为空

堆的大小: 4
堆是否为空: false

通过这个步骤，我们可以清楚地看到 MinHeap 类是如何管理元素的插入、删除和维护堆的性质的。

原文地址：https://blog.csdn.net/hummhumm/article/details/140291970

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：简述 JS 中对象的创建和拷贝
下一篇：【2024年辽宁省数学建模竞赛】B题详细解析（含有代码与参考论文）

使用 ABAP GIT 发生 IF_APACK_MANIFEST dump
它发生在 CREATE OBJECT lo_manifest_provider TYPE (ls_manifest_implementation-clsname)一起使用，但如果拉取的项目打算安装在
阅读更多2024-11-06
ReactPress—基于React的免费开源博客&CMS内容管理系统
ReactPress 是使用React开发的开源发布平台，用户可以在支持React和MySQL数据库的服务器上架设属于自己的博客、网站。也可以把 ReactPress 当作一个内容管理系统（CMS）来
阅读更多2024-11-06
hhdb数据库介绍(4)
介绍关于hhdb的名词
阅读更多2024-11-06
EasyExcel 学习之导出 “提示问题”
导出提示问题
阅读更多2024-11-06
nginx-proxy-manager实现反向代理+自动化证书(实战)
nginx-proxy-manager
阅读更多2024-11-06
python学习记录14
1.字符串的编码和解码2.字符串的验证3.字符串的拼接4.字符串的去重5.正则表达式
阅读更多2024-11-06
在Java中，实现数据库连接通常使用JDBC
学习总结学习总结1、掌握入门到进阶知识(持续写作中……2、学会数据库入门到入土用法(创作中……3、手把手教你开发炫酷的制作(完善中……4、牛逼哄哄的编程利器技巧(编写中……5、面经吐血整理的技巧(更新
阅读更多2024-11-06
Tomcat中如何指定JDK版本
在Tomcat中指定JDK版本可以通过设置环境变量或修改启动脚本来实现。
阅读更多2024-11-06
2024年三个月自学网络安全（黑客技术）进阶手册。
网络安全可以基于攻击和防御视角来分类，我们经常听到的 “红队”、“渗透测试” 等就是研究攻击技术，而“蓝队”、“安全运营”、“安全运维”则研究防御技术。走安全行业的工程方向的，技术上面其实有很大的重叠
阅读更多2024-11-06
自动化生成和发送报告的Python脚本
通过上述步骤，我们成功编写了一个Python脚本，自动化生成和发送销售报告。这个脚本可以根据需要进行扩展和修改，以适应不同的报告需求。数据源：可以将数据源更改为数据库（如MySQL、PostgreSQ
阅读更多2024-11-06

数据结构第17节 最小堆

最小堆的基本操作：

示例代码：

使用示例：

使用示例：

初始状态

操作 1: 插入元素 10

操作 2: 插入元素 1

操作 3: 插入元素 15

操作 4: 插入元素 5

操作 5: 提取最小元素

操作 6: 插入元素 3

操作 7: 检查堆的大小和是否为空

相关文章

数据结构第17节最小堆