数据结构--堆的实现-大根堆/小根堆/堆排序/堆排序稳定性证明/TOP-K

这篇具有很好参考价值的文章主要介绍了数据结构--堆的实现-大根堆/小根堆/堆排序/堆排序稳定性证明/TOP-K。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

       前言 

        逆水行舟,不进则退!!!     


 

       目录

       认识堆

       堆的创建

        1,向下调整的方法建立堆

        2,以向下调整的方式建立小根堆

        3,向上调整的方式建堆

       堆的插入

       堆的删除       

       堆排序

         堆排序稳定性证明

       TOP-K问题

       实现堆操作的完整代码


       认识堆

        堆其实是一棵完全二叉树,完全二叉树是一种特殊的二叉树,除了最后一层外,每一层都被完全填满,最后一层从左到右填充。       

对于完全二叉树(根节点下标为0)中任意一个下标为 i 的结点,它的左孩子结点下标为2i+1,右孩子结点下标为2i+2, 父节点下标为(i-1) / 2(向下取整)。 

        堆也是存储在数组中,假设 i 为结点在数组中的下标,则有:

                如果 i 为0,则 i 表示的节点为根节点,否则 i 节点的双亲节点为 (i - 1)/2
                如果2 * i + 1 小于节点个数,则节点 i 的左孩子下标为2 * i + 1,否则没有左孩子
                如果2 * i + 2 小于节点个数,则节点 i 的右孩子下标为2 * i + 2,否则没有右孩子


 


       堆的创建

        堆有大根堆和小根堆,大根堆的每个结点的值都大于或等于其子节点的值,而小根堆的每个结点的值都小于或等与其子节点的值。 

        在大根堆中,根节点的值最大,因此也称为最大堆。在小根堆中,根节点的值最小,因此也称为最小堆。  大根堆和小根堆常用于堆排序、优先队列等算法中。

        1,向下调整的方法建立堆

        以建大根堆为例,对某个根节点进行一次向下调整的过程为:从一棵完全二叉树的子树的根节点开始,找出两个孩子结点的最大值,然后与根节点进行比较:如果孩子节点大于其父节点的值,则交换孩子结点与父结点的值,保证根节点的值大于孩子结点的值,然后将被交换的孩子结点作为父结点,检查其的子树是否符合大根堆的特点;如果孩子结点小于其父结点的值,则说明以父结点为根结点的这棵树是大根堆。       

··      向下调整的方法是从一个完全二叉树的最后一个非叶子节点开始,依次往回遍历,直到根节点,保证每一棵子树都是大根堆。

        向下调整的方法是从下往上遍历,但对遍历的每一个子根节点都是从上往下调整。这样遍历的好处是只要能确保根节点的值大于孩子节点的最大值,就可以保证该子树是大根堆。

以向下调整的方式建立大根堆

        

        向下调整部分的代码如下:       

 //建大根堆代码
    public int[] createBigHeap() {

 //从最后一个非叶子结点开始遍历,直到根节点结束
        for(int parent = (usedSize-1-1)/2; parent >= 0; parent--) {
            shiftdownBigHeap(parent, usedSize);
        }

        return elem;
    }

    //大根堆向下调整
    private void shiftdownBigHeap(int parent, int len) {
        int child = parent*2+1;
        while(child  < len) {
            if(child+1 < len && elem[child] < elem[child+1]) {  //这里的两个条件不能交换,否则可能产生越界问题,
                child = child+1;
            }
            //上面代码走完后确保child是两个孩子的最大值
            if(elem[child] > elem[parent]) {  //如果孩子结点值大于父亲结点值
                swap(elem, child, parent);    // 交换子节点和父结点
                parent = child;          //这里是继续向下调整,以子节点作为父结点,
                child = parent*2+1;      //继续向下找子节点
            }else {        //如果子节点小于父结点,就直接退出,因为子树已经是调整好的大根堆了
                break;
            }
        }
    }


    private void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
        2,以向下调整的方式建立小根堆

        小根堆与大根堆的区别就在于根节点的值要小于等于孩子结点的最小值。其他的都一样,也是从最后一个非叶子结点开始遍历,直到根结点结束。

以向下调整的方式建立小根堆

        向下调整建立小根堆的代码如下

 private void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    //建小根堆代码
    public int[] createSmallgHeap() {


        for(int parent = (usedSize-1-1)/2; parent >= 0; parent--) {
            shiftdownSmallHeap(parent, usedSize);
        }

        return elem;
    }

    //小根堆向下调整
    private void shiftdownSmallHeap(int parent, int len) {
        int child = parent*2+1;
        while(child  < len) {
            if(child+1 < len && elem[child] > elem[child+1]) {  //这里的两个条件不能交换,否则可能产生越界问题,
                child = child+1;
            }
            //上面代码走完后确保child是两个孩子的最大值
            if(elem[child] < elem[parent]) {
                swap(elem, child, parent);
                parent = child;
                child = parent*2+1;
            }else {
                break;
            }
        }
    }

               

向下调整的方式建堆的时间复杂度:O(N) = N; 

        向下调整时间复杂度的推导:

        

小根堆的实现,数据结构,数据结构,java,算法

        3,向上调整的方式建堆

        向上调整一般用于堆的插入,虽说也可以用来建堆,但是是以插入的方式进行,时间复杂度较高,一般情况下我们是不使用这种方式建堆的。不过这里还是分析一下。

        向上调整的方式建堆,就是将数组中的每个元素,依次插入到堆中,每插入一个元素,进行一次向上调整。以建大根堆为例

向上调整建立大根堆

        向上调整建立大根堆的代码如下:

 public void shiftUpSetHeap() {
        int[] array = new int[10];
        int usedsize = 0;
        for(int i = 0; i < elem.length; i++) {
            array[i] = elem[i];
            shiftUp(i,array);
            usedsize++;
        }
    }
    
    //向上调整
    private void shiftUp(int child, int[] elem) {
        int parent = (child-1)/2;
        while(child > 0) {
            if(elem[child] > elem[parent]) {
                swap(elem, child, parent);
                child = parent;
                parent = (child -1 )/2;
            }else {
                break;
            }
        }
    }

向上调整的时间复杂度为:O(N) =  N*logN;

         向上调整时间复杂度的推导:

小根堆的实现,数据结构,数据结构,java,算法


       堆的插入

        堆的插入已经很清晰明了了,上述的向上调整建堆就是用插入的方式进行建堆的。将插入的元素放到最后,对插入的元素进行向上调整。与建堆不同的是,多了一个判断的操作,判断数组是否满了,满了的话就二倍扩容。

小根堆的实现,数据结构,数据结构,java,算法

    //向上调整
    private void shiftUp(int child, int[] elem) {
        int parent = (child-1)/2;
        while(child > 0) {
            if(elem[child] > elem[parent]) {
                swap(elem, child, parent);
                child = parent;
                parent = (child -1 )/2;
            }else {
                break;
            }
        }
    }
    public void push (int val) {
        if(isFull()){
            elem = Arrays.copyOf(elem, 2*elem.length);
        }
        elem[usedSize] = val;
        //向上调整
        shiftUp(usedSize,elem);
        usedSize++;
    }


    //判满
    public boolean isFull() {
        return usedSize == elem.length;
    }



       堆的删除       

        堆的删除与堆的插入由异曲同工之妙,堆的每次删除都是删除堆的根结点,也就是将堆的根结点与最后一个叶子结点进行交换,然后对新的根结点进行向下调整,最后将usedSize--;就删除完成了。要删除的结点本质上还在数组中,但是usedSize已将将其标记为不可访问。同样的是,堆的删除中也多了一个判断处理,判断数组是否为空。

其实计算机中的绝大多数的删除操作都是如此,并不是将要删除的元素从内存中剔除,而是标记为可使用的新空间,当新的数据将新空间的上一个值覆盖后,那个数据才算从计算机中剔除了。所以删除操作是可以进行恢复的,只是恢复的是那些还没有被覆盖的空间中的值。

 

    //交换
    private void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    //判空
    public boolean isEmpty() {
        return usedSize == 0;
    }

    //堆的删除
    public int pop() {
        if(isEmpty()) {
            return -1;
        }
        int tmp = elem[0];
        swap(elem,0, usedSize-1);
        //shiftdownSmallHeap(0, usedSize-1);
        shiftdownBigHeap(0, usedSize-1);
        usedSize--;
        return tmp;
    }
    

       堆排序

        实现堆排序,最重要的问题就是,无论大根堆还是小根堆都只是层次间有序,具体到层内就是无序的。也就是说根结点的左右孩子的顺序是不确定的。所以我们应该如何使整个堆变得有序?

        其实这个问题的思路在堆的删除中已经给出了,将堆顶元素与最后一个元素进行交换,然后对新的堆顶元素进行向下调整。因为堆顶是最大或最小的元素,此时最后一个元素已经有序。如此反复,就可以将整个堆进行排序。堆排序的代码很简单,主要就是看思路能不能想通。

        如果要实现从小到大排序,那么我们要先建好大根堆。

小根堆的实现,数据结构,数据结构,java,算法

小根堆的实现,数据结构,数据结构,java,算法

小根堆的实现,数据结构,数据结构,java,算法

小根堆的实现,数据结构,数据结构,java,算法

小根堆的实现,数据结构,数据结构,java,算法

小根堆的实现,数据结构,数据结构,java,算法

小根堆的实现,数据结构,数据结构,java,算法

小根堆的实现,数据结构,数据结构,java,算法

小根堆的实现,数据结构,数据结构,java,算法

//已经建好大根堆
//堆排序
    public void heapSort() {
        int end = usedSize-1;
        while(end > 0) {
            swap(elem,0,end);
            shiftdownBigHeap(0,end);
            end--;
        }
    }

       

计算:建堆的时间复杂度 O(N) = N    加上  堆排序的时间复杂度O(N) = N*logN;

堆排序的时间复杂度:O(N) =  N + N*logN  约等于  O(N) = N*logN;

堆排序的空间复杂度:O(1);

        又有一个新的问题,堆排序是否稳定?我们用一组例子来证明。

         堆排序稳定性证明

小根堆的实现,数据结构,数据结构,java,算法

小根堆的实现,数据结构,数据结构,java,算法

结论: 

堆排序的时间复杂度:O(N) =  N + N*logN  约等于  O(N) = N*logN;

堆排序的空间复杂度:O(1);

                      稳定性:堆排序不稳定。


       TOP-K问题

问题:在大量数据中,取出其最大或最小的前K个数 

类似问题:高考前50名,世界500强,富豪榜等问题。

        对于TOP-K问题,能想到的最简单直接的解决方式就是排序,但是:如果数据量过大,排序就不现实了(因为可能内存无法加载全部数据)。此时,就可以考虑用堆来解决。

求:在10000个数据中找前K个最小的元素

解:

        1,取前K个元素,建立大小为K的大根堆,此时堆顶元素为前K个元素中最大的;

        2,从第K+1个元素开始,依次与堆顶元素进行比较,如果某个元素比堆顶元素小,那么先删除堆顶元素,再将该元素插入堆中,然后再进行向上调整,确保堆为大根堆。如此往复,遍历完10000-K个 元素后,此时的堆,就是前K个最小的元素。

理解:就好似用漏斗过滤一般。当找前K个最大的元素时,就取前K个元素建立小根堆,原理同上。


       实现堆操作的完整代码

         

import java.util.Arrays;

public class TestHeap {
    public int[] elem;
    public int usedSize;

    public TestHeap(){
        this.elem = new int[10];
    }

    public void initElem(int[] array) {

        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
    }

    //建大根堆代码
    public int[] createBigHeap() {


        for(int parent = (usedSize-1-1)/2; parent >= 0; parent--) {
            shiftdownBigHeap(parent, usedSize);
        }

        return elem;
    }

    //大根堆向下调整
    private void shiftdownBigHeap(int parent, int len) {
        int child = parent*2+1;
        while(child  < len) {
            if(child+1 < len && elem[child] < elem[child+1]) {  //这里的两个条件不能交换,否则可能产生越界问题,
                child = child+1;
            }
            //上面代码走完后确保child是两个孩子的最大值
            if(elem[child] > elem[parent]) {
                swap(elem, child, parent);
                parent = child;
                child = parent*2+1;
            }else {
                break;
            }
        }
    }

    public void showHeap() {
        for (int i = 0; i < usedSize; i++) {

            System.out.print(elem[i]+" ");
        }
    }

    private void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    //建小根堆代码
    public int[] createSmallgHeap() {


        for(int parent = (usedSize-1-1)/2; parent >= 0; parent--) {
            shiftdownSmallHeap(parent, usedSize);
        }

        return elem;
    }

    //小根堆向下调整
    private void shiftdownSmallHeap(int parent, int len) {
        int child = parent*2+1;
        while(child  < len) {
            if(child+1 < len && elem[child] > elem[child+1]) {  //这里的两个条件不能交换,否则可能产生越界问题,
                child = child+1;
            }
            //上面代码走完后确保child是两个孩子的最大值
            if(elem[child] < elem[parent]) {
                swap(elem, child, parent);
                parent = child;
                child = parent*2+1;
            }else {
                break;
            }
        }
    }

    /*public void shiftUpSetHeap() {
        int[] array = new int[10];
        int usedsize = 0;
        for(int i = 0; i < elem.length; i++) {
            array[i] = elem[i];
            shiftUp(i,array);
            usedsize++;
        }
    }*/

    //向上调整
    private void shiftUp(int child, int[] elem) {
        int parent = (child-1)/2;
        while(child > 0) {
            if(elem[child] > elem[parent]) {
                swap(elem, child, parent);
                child = parent;
                parent = (child -1 )/2;
            }else {
                break;
            }
        }
    }
    public void push (int val) {
        if(isFull()){
            elem = Arrays.copyOf(elem, 2*elem.length);
        }
        elem[usedSize] = val;
        //向上调整
        shiftUp(usedSize,elem);
        usedSize++;
    }


    //判满
    public boolean isFull() {
        return usedSize == elem.length;
    }

    //判空
    public boolean isEmpty() {
        return usedSize == 0;
    }

    //堆的删除
    public int pop() {
        if(isEmpty()) {
            return -1;
        }
        int tmp = elem[0];
        swap(elem,0, usedSize-1);
        //shiftdownSmallHeap(0, usedSize-1);
        shiftdownBigHeap(0, usedSize-1);
        usedSize--;
        return tmp;
    }

}

        我是专注学习的章鱼哥~文章来源地址https://www.toymoban.com/news/detail-765095.html

到了这里,关于数据结构--堆的实现-大根堆/小根堆/堆排序/堆排序稳定性证明/TOP-K的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【数据结构】堆(Heap):堆的实现、堆排序、TOP-K问题

    目录 堆的概念及结构 ​编辑 堆的实现  实现堆的接口 堆的初始化 堆的打印 堆的销毁 获取最顶的根数据  交换 堆的插入(插入最后) 向上调整(这次用的是小堆) 堆的删除(删除根) 向下调整(这次用的小堆) 堆排序 TOP-K问题 如果有一个关键码的集合 K = { , , , …

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

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

    2024年02月03日
    浏览(38)
  • 数据结构——堆的应用 堆排序详解

    hello hello~ ,这里是大耳朵土土垚~💖💖 ,欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹 💥 个人主页:大耳朵土土垚的博客 💥 所属专栏:数据结构学习笔记 💥对于数据结构顺序表、链表、堆有疑问的都可以在上面数据结构的专栏进行学习哦~ 有问题可以写在评论区或者私信

    2024年03月11日
    浏览(50)
  • 【数据结构】堆:堆的构建,堆的向上调整算法,堆的向下调整算法、堆排序

    目录 一、堆的定义 1、堆的定义: 2、根节点与其左、右孩子间的联系   二、堆的创建 1、堆的向下调整算法  2、堆的向上调整算法  三、堆排序 1、堆的定义: 堆可以被看作是 一棵 完全二叉树 的 数组 对象 。即在 存储结构上是数组,在逻辑结构上是一棵完全二叉树 。在

    2024年01月22日
    浏览(43)
  • 数据结构:堆的应用(堆排序和topk问题)

    个人主页 : 个人主页 个人专栏 : 《数据结构》 《C语言》 堆排序即是 先将数据建堆,再利用堆删除的思想来排序。 将待排序数组建堆 将堆顶数据与数组尾部数据交换 调整新的堆顶数据,使其保证堆的结构不变 重复2,3步直到堆中没有数据结束。 降序 建小堆 (父节点 小于

    2024年02月13日
    浏览(38)
  • (Java)数据结构——排序(第一节)堆排序+PTA L2-012 关于堆的判断

    本博客是博主用于复习数据结构以及算法的博客,如果疏忽出现错误,还望各位指正。 堆排序是一种基于堆数据结构的排序算法,其核心思想是将待排序的序列构建成一个最大堆(或最小堆),然后将堆顶元素与最后一个元素交换,再将剩余元素重新调整为最大堆(或最小堆

    2024年04月12日
    浏览(40)
  • 数据结构进阶篇 之 【堆的应用】(堆排序,TOP-K问题)详细讲解

    所有人都关心我飞的高不高,只有我妈关心我翅膀硬不硬 1.1 建堆 1.2 利用堆删除思想来进行排序 –❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀-正文开始-❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀– 学习一个知识,我们起码要直

    2024年04月10日
    浏览(45)
  • 【数据结构】长篇详解堆,堆的向上/向下调整算法,堆排序及TopK问题

    堆就是将一组数据所有元素按完全二叉树的顺序存储方式存储在一个 一维数组 中,并满足树中 每一个父亲节点都要大于其子节点 称为 大堆 (树中 每一个父亲节点都要大于其子节点 称为 小堆 )。 性质 ①对于大堆(大根堆)来说,堆的顶部也就是数组首元素一定是最大的元素 ②

    2024年02月07日
    浏览(40)
  • 【数据结构】向上调整建堆和向下调整建堆的天壤之别以及堆排序算法

       💯 博客内容:【数据结构】向上调整建堆和向下调整建堆的天壤之别以及堆排序算法 😀 作  者:陈大大陈 🚀 个人简介:一个正在努力学技术的准前端,专注基础和实战分享 ,欢迎私信! 💖 欢迎大家:这里是CSDN,我总结知识和写笔记的地方,喜欢的话请三连,有

    2024年02月06日
    浏览(46)
  • 数据结构:堆的实现

    如果有一个关键码的集合 K = { k1 ,k2 ,k3 ,…,kn },把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中,并且 k(i)  k(i*2+1) 和 k(i)  k(i*2+2), i = 0 , 1 , 2…,则称为小堆 ( 或大堆 ) 。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小

    2024年02月13日
    浏览(33)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包