数据结构-最小堆

介绍

数据结构是计算机科学中组织和处理数据的基本工具。其中一种数据结构是最小堆（也称为min-heap），广泛应用于计算机科学、数学和工程等各个领域。本文是最小堆、其属性和应用的介绍。

大话最小堆

从前有一群小动物们需要管理一堆不同大小的食物。他们想要找到一种方式来快速找到最小的食物。于是，他们找到了一个叫做最小堆的东西。最小堆就像是一堆排成一排的食物，其中每个食物都有一个数字，代表它的大小。最小堆中最小的食物总是排在最前面。这就像是一群小动物把所有食物按照大小排序，最小的食物排在最前面。当小动物们需要找到最小的食物时，他们只需要从最小堆的最前面取出食物，就能得到最小的食物了。这就像是小动物们只需要找到最前面的食物，就能找到最小的食物。
但是，当小动物们取出了最小的食物后，最小堆就会发生变化，因为最小的食物不再在最前面了。小动物们需要重新排列食物的顺序，以确保最小的食物仍然在最前面。这就像是小动物们需要重新排列食物的顺序，确保最小的食物仍然在最前面。
通过最小堆，小动物们能够快速找到最小的食物，而不需要花费太多时间去搜索整个食物堆。

最小堆的特性

最小堆是一种二叉树数据结构，其中每个父节点的值小于或等于其子节点的值。换句话说，树的根包含堆中最小的元素。最小堆的这种独特属性使其在各种应用中非常有用，包括排序算法、图算法和数据压缩。
最小堆可以作为数组或链表实现，其中树的根位于数组的第一个元素处。 数组或链表中的每个元素表示二叉树中的一个节点，节点的左右孩子可以分别在2i + 1和2i + 2索引处找到，其中i是父节点的索引。

最小堆的应用

最小堆在像堆排序这样的排序算法中是一种最常用的应用之一。在堆排序中，输入数组首先被转换为最小堆，然后根元素与堆的最后一个元素交换。每次交换后，堆的大小会减少一个，并且剩余的元素会重新组织以维护最小堆属性。这个过程一直持续到整个数组按升序排序为止。最小堆的另一个应用是在图算法中，例如Prim算法用于查找图的最小生成树(MST)。在Prim算法中，使用最小堆来存储图的顶点，其中每个顶点的优先级是其到MST的距离。然后，算法重复从堆中提取最小顶点，并将其相邻的顶点添加到堆中，并更新它们的距离。

代码实现

public class MinHeap {
   

    private int[] heap;
    private int size;

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

    private void siftUp(int index) {
   
        int parent = (index - 1
1
2
3
4
5
6
7
8
9
10
11
12
13