首页 > 其他分享 >堆排序之前篇：关于堆

堆排序之前篇：关于堆

时间：2023-07-09 18:12:18浏览次数：42  
标签：int 元素 堆排序 之前 关于 数组 array 节点 二叉树

 

 

1.  堆的定义和性质

堆是一种特殊的数据结构，它是一颗完全二叉树，且满足以下性质：

  • 堆中某个节点的值总是不大于或不小于其父节点的值。如果父节点的值不大于其子节点的值，这样的堆称为最小堆；如果父节点的值不小于其子节点的值，这样的堆称为最大堆。
  • 堆可以用数组来存储，因为它是完全二叉树，所以可以利用数组的索引来快速访问任意节点。
    • 设当前节点的索引为i，
    • 则其父节点的索引为i/2（向下取整），
    • 其左孩子的索引为2i，其右孩子的索引为2i+1

堆是一种高效的数据结构，它可以快速地找到最大值或最小值，并且进行插入和删除操作。堆的主要应用有：

  • 优先队列：优先队列是一种抽象数据类型，它可以按照元素的优先级顺序出队。优先队列可以用堆来实现，每次出队时，取出堆顶元素，并调整堆的结构。
  • 堆排序：堆排序是一种基于比较的排序算法，它利用堆的性质来对数组进行排序。堆排序分为两个步骤：建堆和排序。建堆是将一个无序数组调整成一个堆；排序是每次将堆顶元素与最后一个元素交换，并缩小堆的范围，直到只剩下一个元素。

 

2. 拓展知识点

2.1  堆为什么叫堆，

  • 一种说法是，堆这个词来源于英文单词heap，heap的本意是一堆东西，可以想象成一堆沙子或者石头，它们是无序的，但是如果我们想要从中找到最大或者最小的一个，只需要从最上面开始找就可以了，不需要遍历整个堆。这和堆这种数据结构的特点很相似，它也是一种无序的集合，但是可以在O(1)时间内找到最大或者最小的元素。

2.2   堆和普通树的区别

堆和普通树的区别主要有以下几点：

  • 堆是一种特殊的完全二叉树，它的每个节点都满足堆的性质，即父节点的值不大于或不小于其子节点的值。而普通树可以是任意形状的，没有这样的性质限制。
  • 堆可以用数组来存储，因为它是完全二叉树，所以可以利用数组的索引来快速访问任意节点。而普通树一般需要用指针来存储，占用更多的空间，并且访问速度较慢。
  • 堆的主要操作是插入和删除，它们都可以在O(logn)时间内完成，并且保持堆的性质。而普通树的操作可能更多样化，比如搜索，遍历，旋转等，它们的时间复杂度也不一定是O(logn)
  • 堆的主要应用是优先队列和排序，它可以快速地找到最大值或最小值，并且进行插入和删除。而普通树的应用可能更广泛，比如搜索树，平衡树，字典树等，它们可以解决不同类型的问题

 

2.3   完全二叉树 是指什么

完全二叉树是一种特殊的二叉树，它的定义如下：

  • 完全二叉树是一棵深度为k的有n个结点的二叉树，
    • 对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
  • 完全二叉树除了最后一层外，其它各层的结点数都达到最大个数，第k层所有的结点都连续集中在最左边
  • 完全二叉树可以用数组来存储，利用数组的索引来快速访问任意节点
  • 完全二叉树具有n个结点的深度为floor(log2n)+1，其中floor表示向下取整

2.4   堆和完全二叉树的区别

堆和完全二叉树的区别主要有以下几点：

  • 堆是一种特殊的完全二叉树，它满足父节点的值总是不大于或不小于其子节点的值，称为堆序性。完全二叉树只要求除了最后一层外，其他层的节点都是满的，且最后一层的节点都靠左。
  • 堆可以分为最大堆和最小堆，最大堆的父节点的值总是不小于其子节点的值，最小堆的父节点的值总是不大于其子节点的值。完全二叉树没有这样的分类。
  • 堆可以用数组来表示，因为完全二叉树有一个性质：对于任意一个父节点的序号n来说（这里n从0算），它的子节点的序号一定是2n+1,2n+2。完全二叉树也可以用数组来表示，但不一定能保持堆序性。
  • 堆可以用来实现优先级队列，也可以用来进行堆排序。优先级队列可以在O(log n)时间内插入或删除元素，并且O(1)时间内查询最大（或最小）元素。堆排序的基本思想是：首先建立一个堆，然后将堆顶元素与最后一个元素交换，然后将剩余的元素重新调整为堆，重复这个过程，直到所有元素有序。完全二叉树没有这样的应用。

 

 2.5   大顶堆和小顶堆的应用场景

大顶堆和小顶堆的应用场景主要取决于我们想要从一组数据中快速地找到最大值或者最小值，或者是找到第k大或者第k小的值。一般来说，有以下几种常见的应用场景：

  • 堆排序：堆排序是一种基于堆的排序算法，它的基本思想是：首先建立一个大顶堆或者小顶堆，然后将堆顶元素与最后一个元素交换，然后将剩余的元素重新调整为堆，重复这个过程，直到所有元素有序。这个算法可以在O(nlogn)时间内完成，并且只需要O(1)的额外空间。
  • 优先级队列：优先级队列是一种数据结构，它可以让我们在任意时刻都能快速地找到优先级最高（或最低）的元素，并且可以在O(logn)时间内插入或删除元素。优先级队列可以用堆来实现，一般使用小顶堆表示优先级最高的元素在堆顶，或者使用大顶堆表示优先级最低的元素在堆顶。优先级队列有很多应用场景，比如定时任务轮询，合并有序小文件，Dijkstra算法等。
  • Top K问题：Top K问题是指从一组数据中找出最大（或最小）的K个元素。这个问题可以用堆来解决，一般使用一个大小为K的小顶堆来维护最大的K个元素，或者使用一个大小为K的大顶堆来维护最小的K个元素。每次遇到一个新的元素，就和堆顶元素比较，如果比它大（或小），就替换掉它，并重新调整堆。这样可以在O(nlogk)时间内解决这个问题。
  • 中位数和百分位数问题：中位数和百分位数问题是指从一组数据中找出中间位置（或某个百分比位置）的元素。这个问题也可以用堆来解决，一般使用一个大顶堆和一个小顶堆来维护数据的两个部分，使得两个堆的大小之差不超过1，并且大顶堆的所有元素都小于等于小顶堆的所有元素。每次遇到一个新的元素，就根据它和两个堆顶元素的大小关系，将它插入到合适的堆中，并且保持两个堆的平衡。这样可以在O(logn)时间内插入一个元素，并且在O(1)时间内找到中位数（或百分位数）。

如果你想了解更多关于大顶堆和小顶堆的应用场景，你可以参考以下链接：

 

3. 堆的基本操作

3.1  插入

插入操作是向堆中添加一个新元素，使得堆仍然保持其性质。插入操作的步骤如下：

  • 将新元素放到数组末尾，即作为完全二叉树的最后一个叶子节点。
  • 将新元素与其父节点比较，如果新元素小于（或大于）其父节点，则交换它们的位置。
  • 重复上一步，直到新元素到达根节点或者不再小于（或大于）其父节点。

例如，下图展示了在一个最小堆中插入元素8的过程：

 

插入操作的时间复杂度为O(logn)，其中n为堆中元素个数。

3.2  删除

删除操作是从堆中移除一个元素，通常是移除堆顶元素，即最小值或最大值。删除操作的步骤如下：

  • 将数组末尾的元素替换到根节点，即作为完全二叉树的新根节点。
  • 将新根节点与其左右孩子中较小（或较大）的一个比较，如果新根节点大于（或小于）其左右孩子中较小（或较大）的一个，则交换它们的位置。
  • 重复上一步，直到新根节点到达叶子节点或者不再大于（或小于）其左右孩子中较小（或较大）的一个。

例如，下图展示了从一个最小堆中删除元素0（即堆顶元素）的过程：

 

删除操作的时间复杂度为O(logn)，其中n为堆中元素个数。

3.3  建堆

建堆操作是将一个无序数组调整成一个堆，使得堆中的每个节点都满足堆的性质。建堆操作的步骤如下：

  • 从最后一个非叶子节点开始，对每个节点执行下沉操作，即将该节点与其左右孩子中较小（或较大）的一个比较，如果该节点大于（或小于）其左右孩子中较小（或较大）的一个，则交换它们的位置，然后继续对交换后的位置执行下沉操作，直到该节点到达叶子节点或者不再大于（或小于）其左右孩子中较小（或较大）的一个。
  • 重复上一步，直到遍历到根节点。

例如，下图展示了将一个无序数组[5, 3, 8, 4, 1, 2, 6, 7]调整成一个最小堆的过程：

 

建堆操作的时间复杂度为O(n)，其中n为数组元素个数。

 

4.  堆的代码实现

堆的代码实现

下面给出了使用Java实现最小堆的代码示例：

// 定义堆类
public class MinHeap {
    // 定义数组属性
    private int[] array;

    // 初始化堆
    public MinHeap(int[] array) {
        this.array = array;
        this.buildHeap();
    }

    // 返回堆中元素个数
    public int size() {
        return array.length;
    }

    // 判断堆是否为空
    public boolean isEmpty() {
        return size() == 0;
    }

    // 返回父节点索引
    public int parent(int i) {
        return (i - 1) / 2;
    }

    // 返回左孩子索引
    public int left(int i) {
        return 2 * i + 1;
    }

    // 返回右孩子索引
    public int right(int i) {
        return 2 * i + 2;
    }

    // 下沉操作
    public void sink(int i) {
        int n = size();
        while (left(i) < n) { // 如果有左孩子
            int j = left(i); // j为左孩子索引
            if (right(i) < n && array[right(i)] < array[j]) { // 如果有右孩子且右孩子小于左孩子
                j = right(i); // j为右孩子索引
            }
            if (array[i] <= array[j]) { // 如果当前节点小于等于较小的孩子
                break; // 停止下沉
            }
            swap(i, j); // 否则交换当前节点和较小的孩子
            i = j; // 更新当前节点索引
        }
    }

    // 上浮操作
    public void swim(int i) {
        while (i > 0 && array[i] < array[parent(i)]) { // 如果当前节点小于其父节点
            swap(i, parent(i)); // 交换当前节点和父节点
            i = parent(i); // 更新当前节点索引
        }
    }

    // 建堆操作
    public void buildHeap() {
        for (int i = size() / 2 - 1; i >= 0; i--) { // 从最后一个非叶子节点开始
            sink(i); // 对每个节点执行下沉操作
        }
    }

    // 插入操作
    public void insert(int x) {
        int[] newArray = new int[size() + 1]; // 创建一个新的数组，长度比原数组多1
        System.arraycopy(array, 0, newArray, 0, size()); // 将原数组的元素复制到新数组中
        newArray[size()] = x; // 将新元素放到新数组末尾
        array = newArray; // 更新数组属性为新数组
        swim(size() - 1); // 对新元素执行上浮操作
    }

    // 删除操作
    public int delete() {
        if (isEmpty()) { // 如果堆为空，抛出异常
            throw new RuntimeException("Heap is empty");
        }
        int min_value = array[0]; // 记录堆顶元素，即最小值
        array[0] = array[size() - 1]; // 将数组末尾的元素替换到根节点
        int[] newArray = new int[size() - 1]; // 创建一个新的数组，长度比原数组少1
        System.arraycopy(array, 0, newArray, 0, size() - 1); // 将原数组除了最后一个元素外的其他元素复制到新数组中
        array = newArray; // 更新数组属性为新数组
        sink(0); // 对根节点执行下沉操作
        return min_value; // 返回最小值
    }

    // 交换两个元素的位置的辅助方法
    private void swap(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

}

堆的测试

下面给出了使用堆来实现优先队列和堆排序的测试代码：


// 测试优先队列
public static void testPriorityQueue() {
    System.out.println("Testing priority queue...");
    MinHeap heap = new MinHeap(new int[]{5, 3, 8, 4, 1, 2, 6, 7}); // 创建一个最小堆
    System.out.println("The heap is: " + Arrays.toString(heap.array)); // 打印堆
    heap.insert(0); // 插入一个新元素
    System.out.println("After inserting 0, the heap is: " + Arrays.toString(heap.array)); // 打印堆
    int min_value = heap.delete(); // 删除堆顶元素
    System.out.println("After deleting the minimum value, the heap is: " + Arrays.toString(heap.array)); // 打印堆
    System.out.println("The minimum value is: " + min_value); // 打印最小值
}

// 测试堆排序
public static void testHeapSort() {
    System.out.println("Testing heap sort...");
    int[] array = new int[]{5, 3, 8, 4, 1, 2, 6, 7}; // 创建一个无序数组
    System.out.println("The original array is: " + Arrays.toString(array)); // 打印数组
    MinHeap heap = new MinHeap(array); // 创建一个最小堆
    int[] sorted_array = new int[array.length]; // 创建一个空数组用来存放排序后的元素
    for (int i = 0; i < array.length; i++) { // 当堆不为空时
        sorted_array[i] = heap.delete(); // 将堆顶元素加入到排序后的数组中，并删除堆顶元素
    }
    System.out.println("The sorted array is: " + Arrays.toString(sorted_array)); // 打印排序后的数组
}

// 主函数
public static void main(String[] args) {
    testPriorityQueue(); // 测试优先队列
    testHeapSort(); // 测试堆排序
}

运行结果如下：

Testing priority queue...
The heap is: [1, 3, 2, 4, 5, 8, 6, 7]
After inserting 0, the heap is: [0, 3, 1, 4, 5, 8, 6, 7, 2]
After deleting the minimum value, the heap is: [1, 3, 2, 4, 5, 8, 6, 7]
The minimum value is: 0
Testing heap sort...
The original array is: [5, 3, 8, 4, 1, 2, 6, 7]
The sorted array is: [1, 2, 3, 4, 5, 6, 7, 8]

5. 堆的总结

堆是一种非常有用的数据结构，它可以快速地找到最大值或最小值，并且进行插入和删除操作。堆的主要应用有优先队列和堆排序。堆可以用数组来存储，利用完全二叉树的性质来快速访问任意节点。堆的基本操作有插入、删除和建堆，它们的时间复杂度都是O(logn)或O(n)。使用Python实现了最小堆的代码，并且给出了测试示例。

如果你想了解更多关于堆的知识，你可以参考以下链接：

 

 

6. refer

 

标签：int,元素,堆排序,之前,关于,数组,array,节点,二叉树
From： https://www.cnblogs.com/shoshana-kong/p/17530706.html

相关文章

  • 关于vue在列表展示数据的时候，更改其中一项，列表没有跟着实时变动的问题
    背景：使用低代码自动生成的Vue前端大致页面，然后自定义其中的业务涉及的页面： 遇到的问题：点击添加后，直接变更添加行的状态（输入框不可编辑、状态变为已激活）涉及代码：addRecordAndApply(index){letthatthis=this;letindexData=this.dataList[index];......
  • 关于django-storages
    如果djangofileField,imageField不是默认存在本地服务器，而是远程云服务器上，则使用django-storages可以对应很多云服务器如AmazonS3AzureStorageDropBoxGoogleCloudStorageApacheLibcloudFTP/SFTP 文件保存访问路径django默认MEDIA_ROOTMED......
  • 配置steam input遇到的坑,调用steam input API 之前的准备工作
    配置steaminput遇到的坑,调用steaminputAPI之前的准备工作 总共需要3种类型的文件1.steam_appid.txt这个文件里面就只有一个id,对应着你正在调试的app,这个文件必须放在你生成的game.exe旁边比如在vc的Debug文件夹中,或者工程的根目录下.缺这个文件SteamAPI_Init无法调......
  • 关于Azure-平台-Redhat-Linux-服务器时间同步的问题解决
    首先说明一下，关于Azure平台中国区，是没有RedhatLinux系统镜像的于是笔者这边是通过在Windows系统 Hyper-V管理器中安装完Redhat8.x操作系统后，最后将系统磁盘转换成转换为VHD格式然后经过一系列操作、最终在Azure平台上形成了自己的并且加固过的RedHatEnterpriseLinuxre......
  • 关于Stream流的一些常用方法
    前言在这里先说明一下，这个重在应用，本文就不对概念跟描述做过多赘述。应用1）提取对象数组中的某一个字段(带去重)List<String>orderIdList=orderList.stream().map(e->e.getOrderId()).distinct().collect(Collectors.toList());//收集全部orderIdSetthirdCategoryI......
  • 关于接口和抽象类
    接口（Interface）和抽象类（AbstractClass）用于实现代码的抽象和封装。定义方式：接口是一种纯粹的抽象概念，只定义了方法的签名，没有实现；抽象类是一个可以包含抽象方法和具体方法的类。实现方式：一个类可以实现多个接口；一个类只能继承一个抽象类。方法：接口中的方法默认是公共的抽......
  • 关于手打栈（Stack)的最基本用法
    写在前面这是本蒟蒻的第一篇博客。毕竟不是题解，也没有冠以题解的名号。作者就是个时常不带脑子的傻瓜，因此定有错误、不足之处，还请多多包涵，并欢迎批评指正！栈栈（stack）是一种数据结构，在STL标准库中可以直接使用。具体地说，栈就是一种只允许在一端进行插入或删除操作的线性表。与队列......
  • 关于通过bat脚本-自动使用mstsc-远程桌面命令登录到远程windows主机的方法
    在Windows系统中，我们可以通过系统自带的mstsc远程桌面工具，登录到远端的windows服务器主机但是需要输入用户名和密码，回车、于是笔者想了一下，能不能创建一个bat文件，双击后，就会自动的传入用户名和密码进行登录经过查询和实验、还真有这样的办法（当然在正式的环境，不建议这样操作，因为......
  • java 关于数据库外键
    查询性能：当查询涉及到外键关系时，数据库需要进行额外的操作来验证关联关系的完整性，这可能会导致查询速度变慢。特别是在大型数据库系统中，外键的验证操作可能会消耗较多的计算资源和时间。更新性能：当更新外键相关的数据时，数据库需要确保更新操作不会破坏关联关系的完整性。这可......
  • 关于JS定时器的整理
    在JS中定时器有非常大的作用，例如：执行延迟操作：使用setTimeout可以在一定的延迟后执行特定的代码。这对于需要在一定时间后执行某些操作的情况非常有用，例如延迟显示提示信息、执行动画效果等。定期刷新数据：使用setInterval可以定期执行某段代码，例如定时从服务器获取最新数据并......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99