Java之堆和堆排序

这篇具有很好参考价值的文章主要介绍了Java之堆和堆排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一.什么是堆

1.基本介绍

2.堆的实现方式

二.最大堆的实现

1.最大堆

2.思路分析

0.基础操作

1.添加+上浮操作

2.删除+下沉操作

3.将数组堆化操作

2.代码实现

三.堆排序

1.什么是堆排序

2.思路分析

3.代码实现


一.什么是堆

1.基本介绍

堆是一种数据结构,通常被描述为一棵完全二叉树,其中每个节点都满足堆属性。堆有两种类型:最大堆(大顶堆)和最小堆(小顶堆)。在最大堆中,父节点的值大于或等于其子节点的值,而在最小堆中,父节点的值小于或等于其子节点的值。堆常常用于优先队列中,其中最大(或最小)元素总是位于堆的根节点。堆也可以被用作排序算法的一部分,如堆排序

2.堆的实现方式

堆有两种常见的实现方式:二叉堆和斐波那契堆

二叉堆是最常见的堆实现方式,其特点是满足以下两点性质:

  • 堆是一种完全二叉树;
  • 堆中每个节点的值都必须大于等于(或小于等于)其子树中每个节点的值。

由于完全二叉树的性质,我们可以使用数组来表示二叉堆,(根结点为0时)其节点的左孩子在数组中的位置为 2i+1,右孩子的位置为 2i+2,其父节点的位置为 (i-1)/2。

斐波那契堆是另一种常见的堆实现方式,其相较于二叉堆更加高效,但是实现起来也更加复杂。斐波那契堆采用了一种基于树形结构的优化方法,可以支持更加高效的插入、删除和查找操作。但是,斐波那契堆的常数项较大,且实现也更加复杂,因此在实际应用中并不常见

二.最大堆的实现

1.最大堆

最大堆,父节点的值大于或等于其子节点的值,我们通常用数组来表示堆结构,因此(都存在的情况下)结点i的左孩子结点下标为2*i+1,右孩子结点2*i+2,父亲节点为(i-1)/2,每一次添加和删除操作,我们都要保持最大堆的结构性质.

2.思路分析

首先我们用List<Integer>集合来保存堆中的元素,当然我们也可以用数组,但需要考虑扩容,因此为了方便起见,我们直接使用API提供的,底层也是用数组实现的.

0.基础操作

1.交换两个元素

    private void swap(int i, int j) {
        int temp = data.get(i);
        data.set(i, data.get(j));
        data.set(j, temp);
    }

2.返回当前结点左孩子下标

    //返回左子树结点的索引
    public int leftChild(int index) {
        return index * 2 + 1;
    }

3.返回当前结点右孩子下标

    //返回右子树结点的索引
    public int rightChild(int index) {
        return index * 2 + 2;
    }

4.返回当前结点的父节点下标

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

1.添加+上浮操作

首先考虑添加元素的处理:我们首先把元素添加到最后一个位置,也就是索引为size的位置,size++;此时这个元素位置只是临时的,因为我们要保持大顶堆的结构性质:父节点的值大于或等于其子结点的值,这个时候我们需要进行上浮操作(siftup),上浮的位置应该满足当前元素的值大于或等于其子结点的值.例如:{7,4,5,2,3}中添加8元素

Java之堆和堆排序

此时8大于它的父节点5,将8和5进行交换

Java之堆和堆排序

 8大于它的父节点7,将将8和7进行交换

Java之堆和堆排序

 此时8位于根结点,不存在父节点了,因此循环结束

因此我们可以总结出循环结束的两个条件,一个就是当前结点小于根结点,或者当前结点不存在父节点,也就是结点的索引不是0,循环继续的条件则为index>0&&data.get(parent(index)) < data.get(index),因此我们便可以很容易的写出来上浮siftup操作.

    //添加值为val的值到堆中
    public void add(int val) {
        data.add(val);
        size++;
        siftUp(size - 1);
    }


    private void siftUp(int index) {
        //当前结点不是根结点且当前结点大于其父节点
        while (index > 0 && data.get(parent(index)) < data.get(index)) {
            swap(parent(index), index);
            index = parent(index);

        }
    }

2.删除+下沉操作

我们实现的堆每一次删除堆中的最大值,也就是索引为0位置上的元素,我们可以使用这种方式来删除元素,将索引为0的元素和最后一个元素(size-1)进行交换,然后将最后一个元素删除,这样可以保持完全二叉树的结构,也可以实现删除操作.

然后我们调整这个二叉树使其成为堆,因为将最后一个结点交换到第一个结点一定不是堆结构,每一次我们寻找到其孩子结点的最大值,然后将此结点和最大值进行对比,如果大于最大值或者当前结点的左孩子的索引大于size就停止交换,此时就是最大堆了,如果比最大值小,就交换这两个结点

    public int extractMax() {
        if (data.isEmpty()) {
            throw new NoSuchElementException("heap is empty!cannot extract!");
        }

        swap(0, size - 1);
        Integer remove = data.remove(size - 1);
        size--;
        siftDown(0);
        return remove;

    }

    private void siftDown(int index) {
        //确保有左子树
        while (leftChild(index) < size) {
            int j = leftChild(index);
            if (j + 1 < size && data.get(j) < data.get(j + 1)) {
                j = j + 1;
            }
            if (data.get(index) < data.get(j)) {
                swap(index, j);
                index = j;
            } else {
                break;
            }
        }
    }

3.将数组堆化操作

将传入的数组转化为大顶堆,我们可以将数组中的元素一个个调用添加操作,当然可以转化为大顶堆,但我们还是定义一个方法(构造器),来对传入的数组进行堆化操作(在堆排序中使用到).

我们可以从当前完全二叉树的最后一个非叶子结点(parent(size-1))开始向下调整,使得每个子树为转化为堆

    //将arr调整为最大堆
    public MaxHeap(int[] arr) {
        this.data = new ArrayList<>(arr.length);
        for (int i : arr) {
            data.add(i);
            size++;
        }
        //从当前完全二叉树的最后一个非叶子结点向下调整,使每个子树为堆
        for (int i = parent(size - 1); i >= 0; --i) {
            siftDown(i);
        }

    }
    private static void siftDown(int[] arr, int index, int size) {
        //确保有左子树
        while (index * 2 + 1 < size) {
            //左孩子
            int j = index * 2 + 1;
            //左右孩子两者的最大值
            if (j + 1 < size && arr[j] < arr[j + 1]) {
                j = j + 1;
            }
            if (arr[index] < arr[j]) {
                swap(arr, index, j);
                index = j;
            } else {
                break;
            }
        }
    }

2.代码实现

public class MaxHeap {
    private List<Integer> data;
    private int size;


    //将arr调整为最大堆
    public MaxHeap(int[] arr) {
        this.data = new ArrayList<>(arr.length);
        for (int i : arr) {
            data.add(i);
            size++;
        }
        //从当前完全二叉树的最后一个非叶子结点向下调整,使每个子树为堆
        for (int i = parent(size - 1); i >= 0; --i) {
            siftDown(i);
        }

    }
    public MaxHeap() {
        this(10);
    }

    public MaxHeap(int size) {
        this.data = new ArrayList<>(size);
        this.size = 0;
    }

    public int size() {
        return this.size;
    }

    @Override
    public String toString() {
        return data.toString();
    }


    //添加值为val的值到堆中
    public void add(int val) {
        data.add(val);
        size++;
        siftUp(size - 1);
    }

    //返回左子树结点的索引
    public int leftChild(int index) {
        return index * 2 + 1;
    }

    //返回右子树结点的索引
    public int rightChild(int index) {
        return index * 2 + 2;
    }

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


    private void siftUp(int index) {
        //当前结点不是根结点且当前结点大于其父节点
        while (index > 0 && data.get(parent(index)) < data.get(index)) {
            swap(parent(index), index);
            index = parent(index);

        }
    }

    public int extractMax() {
        if (data.isEmpty()) {
            throw new NoSuchElementException("heap is empty!cannot extract!");
        }

        swap(0, size - 1);
        Integer remove = data.remove(size - 1);
        size--;
        siftDown(0);
        return remove;

    }

    private void siftDown(int index) {
        //确保有左子树
        while (leftChild(index) < size) {
            int j = leftChild(index);
            if (j + 1 < size && data.get(j) < data.get(j + 1)) {
                j = j + 1;
            }
            if (data.get(index) < data.get(j)) {
                swap(index, j);
                index = j;
            } else {
                break;
            }
        }
    }

    private void swap(int i, int j) {
        int temp = data.get(i);
        data.set(i, data.get(j));
        data.set(j, temp);
    }


}

希望大家可以自己实现小顶堆的实现,实现思路基本和大顶堆的实现一样.

三.堆排序

1.什么是堆排序

堆排序是一种基于堆数据结构的排序算法,它的时间复杂度为O(n log n)。堆排序的核心思想是将待排序序列构造成一个堆,然后依次将堆顶元素与堆底元素交换,再对剩余的元素重新构造成堆,直到所有元素都有序。由于堆排序是基于完全二叉树的,因此可以使用数组来表示堆,从而节省了树的指针空间的开销。堆排序有两种形式:大根堆和小根堆。在大根堆中,父节点的值大于等于任何一个子节点的值,在小根堆中则相反,父节点的值小于等于任何一个子节点的值。因此,大根堆可以用来进行升序排序,而小根堆则可以用来进行降序排序。堆排序的主要优点是稳定性好,适用于大规模数据的排序。

2.思路分析

其实大部分的操作我们在堆中已经将讲解过了,首先我们对数组堆化操作,转化为一个大顶堆,然后我们每次将堆顶元素和最后一个元素进行交换,因为堆顶元素都是剩下元素的最大元素,因此每次我们都能找到剩下元素中的最大值,每一次交换之后堆的长度就减一,因为之后的元素已经有序了文章来源地址https://www.toymoban.com/news/detail-411763.html

3.代码实现

    //原地堆排序
    public static void heapSort(int[] arr) {
        //将arr堆化
        //从当前完全二叉树的最后一个非叶子结点向下调整,使每个子树为堆
        for (int i = (arr.length - 2) / 2; i >= 0; --i) {
            siftDown(arr, i, arr.length);

        }
        //将堆顶的元素和最后一个交换
        for (int i = arr.length - 1; i >= 0; --i) {
            swap(arr, 0, i);
            siftDown(arr, 0, i);

        }
    }

    private static void siftDown(int[] arr, int index, int size) {
        //确保有左子树
        while (index * 2 + 1 < size) {
            //左孩子
            int j = index * 2 + 1;
            //左右孩子两者的最大值
            if (j + 1 < size && arr[j] < arr[j + 1]) {
                j = j + 1;
            }
            if (arr[index] < arr[j]) {
                swap(arr, index, j);
                index = j;
            } else {
                break;
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

到了这里,关于Java之堆和堆排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构--八大排序】之堆排序

    💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃 个人主页 :阿然成长日记 👈点击可跳转 📆 个人专栏: 🔹数据结构与算法🔹C语言进阶 🚩 不能则学,不知则问,耻于问人,决无长进 🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍 口诀:排降序,建小

    2024年02月08日
    浏览(46)
  • DS:八大排序之堆排序、冒泡排序、快速排序

                                                     创作不易,友友们给个三连吧!!  堆排序已经在博主关于堆的实现过程中详细的讲过了,大家可以直接去看,很详细,这边不介绍了 DS:二叉树的顺序结构及堆的实现-CSDN博客 直接上代码: 建堆的时间复杂度是o(N),

    2024年02月20日
    浏览(38)
  • 用C语言进行学生成绩排序(简单选择排序和堆排序)

    选择排序的基本思想是:每一趟(如第i趟)在后面n-i+1 (i=1,2…,n-1) 个待排序元素中选取最小的元素,作为有序子序列的第i个元素,直到第n-1趟做完,待排序元素只剩下1个,就不用再选了。选择排序中的堆排序算法是历年考查的重点。 根据上面选择排序的思想,可以很直观

    2024年02月15日
    浏览(35)
  • 八大排序算法之堆排序的实现+经典TopK问题

    目录 一.堆元素的上下调整接口 1.前言 2.堆元素向上调整算法接口 3.堆元素向下调整算法接口 二.堆排序的实现 1.空间复杂度为O(N)的堆排序(以排升序为例) 思路分析: 代码实现: 排序测试: ​时空复杂度分析: 2. 空间复杂度为O(1)的堆排序(以排降序为例) 将数组arr调整成堆的思路

    2024年02月02日
    浏览(43)
  • 数据结构与算法之堆排序

    堆排序 (Heap Sort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。如下图: 同时,我们对堆中的结点按

    2024年02月09日
    浏览(42)
  • 【Python排序算法】一文掌握十大排序算法,冒泡排序、插入排序、选择排序、归并排序、计数排序、基数排序、希尔排序和堆排序

    目录 1 冒泡排序(Bubble Sort) 2 插入排序(Insertion Sort) 3 选择排序(Selection Sort) 4. 快速排序(Quick Sort) 5. 归并排序(Merge Sort) 6 堆排序 (Heap Sort) 7 计数排序 (Counting Sort) 8 基数排序 (Radix Sort) 9 希尔排序(Shell Sort) 10 桶排序     1 冒泡排序(Bubble Sort)        冒泡排序

    2024年02月08日
    浏览(55)
  • 排序篇:直接插入、希尔、直接选择和堆排序(C语言)

    目录 前言: 一:插入排序 (1)直接插入排序 基础思路(有个印象就行,主要看单趟) 单趟排序 完整排序 时间复杂度分析 (2)希尔排序 基础思路(有个印象就行,主要看单趟) 单趟排序 完整排序 时间复杂度分析 二:选择排序 (1)直接选择排序 基础思路 单趟排序 完整排序 时间复杂

    2024年02月03日
    浏览(39)
  • 【数据结构】堆的实现(向下调整和向上调整法)和堆排序的实现

    目录 一、堆的概念引入 二、小堆的实现 ①、堆的初始化--HeapInit ②、小堆的向下调整法的实现 ③、堆排序的实现  ④、堆的插入和向上调整法  ⑤、删除堆顶数据 ⑥、获取堆顶 三、时间复杂度总结: 注:本文logN表示以2为底N的对数 普通的二叉树不适合用数组来存储的,因

    2024年02月03日
    浏览(38)
  • 2-Linux 目录介绍及基本指令和操作命令

    一、目录介绍 /:表示的是根的意思 /bin:(binary)存放的是一些二进制文件,但是在Linux中二进制文件是可以被执行的。这个目录中的命令文件是给普通用户使用(非超级管理员用户)。 /etc:Linux下所有的配置文件都会存放到etc目录。 /home:是所有非root用户家目录的一个集

    2024年02月08日
    浏览(48)
  • 数据结构之堆排序以及Top-k问题详细解析

    个人主页:点我进入主页 专栏分类:C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶 C语言刷题       数据结构初阶 欢迎大家点赞,评论,收藏。 一起努力 目录 1.前言 2.堆排序 2.1降序排序 2.2时间复杂度 3.Top-k问题 4.总结         在上一篇文

    2024年02月05日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包