当前位置:首页 > 网络技术 > 堆排序代码解析(堆排序的算法及代码实现)(堆排序 代码)

堆排序代码解析(堆排序的算法及代码实现)(堆排序 代码)

longge2022-03-24 00:19:13网络技术62

目前这个系列的文章都挑着非常经典的,让人眼前一亮的算法,今天的堆排序算法就是其中一个。 首先理解什么是堆,这里面堆(Heap)并不是程序中内存区域,而是一种完全二叉树表示的数据结构。 堆具有以下特点

  • 是一个完全二叉树
  • 堆的每个节点的值必须大于等于左右树节点(大顶堆),或小于等于左右树节点(小顶堆)。

简单说明下,完全二叉树是除了最后一层叶子节点外,其他的节点都有两个子树,而叶子节点可以没有子树,或者只有左子树。 如下图就是个大顶堆:

小顶堆

堆存储

堆因为是完全二叉树,非常适合用数组存储,上图为大顶堆的存储情况,其中a[0]不用, a[1]为大顶堆的顶点,也就是最大的数据,a[12]= 7 为左子树顶点,a[12+1]= 6为右子树的顶点,其他节点情况依次类推。

堆的两种操作

向堆插入元素

用图来表示如下:

向堆插入元素,先插入到最后一个数组元素位置,然后和自己的父节点6比较,由于比6大不满足大顶堆的条件,所以9和6交换,然后9再和堆顶元素8比较,又不满足大顶堆条件,继续交换,最后形成一个大顶堆,这个步骤叫堆化。

删除堆顶元素

对于大顶堆来说,堆顶的元素为最大值,依次删除堆顶元素并输出,那么就是将数字从大向小排列了。

这里面又个技巧,就是删除堆顶元素的时候,不能直接删除,要用堆顶元素和最后一个元素做交换,然后根据堆的特点调整堆,直到满足条件。

完整代码如下:

package com.dianneng.lms;

public class TestHeap {
    private int [] a;
    private int n;
    private int count;

    public TestHeap(int cap) {
        a = new int[cap+1];
        n = cap;
        count = 0;
    }

    public void swap(int i,int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
        return;
    }

    public void print(){
        for (int i = 0; i <= count;i++) {
            System.out.print(a[i]+"t");
        }
    }

    public int insert( int v) {
        if (count == n) {
            System.out.println("Heap is full!");
            return -1;
        }else {
            a[++count] = v;
            int i = count;
            while (i/2 >0 && a[i] > a[i/2]) {
                swap(i,i/2);
                i = i/2;
            }
        }
        return 0;
    }

    public int  removeMax() {
        if (count == 0)  {
            return -1;
        }
        System.out.print(a[1]+"t");
        a[1] = a[count];
        --count;
        heapify(count,1);
        return 0;
    }

    private void heapify(int n, int i) {
        while(true) {
            int maxPos = i;
            //通过左右子树顶点比较获得最大数节点
            if (i*2 <= n && a[i] <a[i*2] ){
                maxPos = i*2;
            }
            if (i*2+1 <= n && a[maxPos] < a[i*2+1]) {
                maxPos = i*2+1;
            }
            //已经是最大的不用交换了
            if  (maxPos == i) {
                break;
            }
            //需要交换
            swap(i,maxPos);
            //i指向待交换的
            i = maxPos;
        }
    }

    public  static void main(String [] args) {
        TestHeap th = new TestHeap(18);
        th.insert(8);
        th.insert(7);
        th.insert(6);
        th.insert(5);
        th.insert(4);
        th.insert(3);
        th.print();
        System.out.println();
        while(th.removeMax() == 0) {

        }
    }
}

可以利用大顶堆的特性,对要排序的数组进行先堆化排序,然后依次交换堆顶元素和最后一个元素,交换后堆化,将堆的大小减一,最终这样输出的就是从小到大排序的数组。 借用老师的一个图表示:

免责声明
本站部分资源来源于互联网 如有侵权 请联系站长删除
龙哥网是优质的互联网科技创业资源_行业项目分享_网络知识引流变现方法的平台为广大网友提供学习互联网相关知识_内容变现的方法。#转载请注明出处!

“堆排序代码解析(堆排序的算法及代码实现)(堆排序 代码)” 的相关文章

Windows Server 2012不同版本官方下载地址

Windows Server 2012不同版本官方下载地址

Windows Server 2012:http://technet.microsoft.com/en-US/evalcenter/hh670538.aspx Windows Server 201...

网页psd源文件photoshop切图工具方法(psd网页切图制作html)

网页psd源文件photoshop切图工具方法(psd网页切图制作html)

网页psd切图我习惯用矩形选框工具,操作简单,自动判断大小,很方便,切图的方法有很多种,这里介绍2种 1. 把psd源文件中除目标图层外,其余图层不显示,使用背景透明,使用矩形选框工具(快捷键...

javascript实现浏览器全屏显示和退出全屏代码(js控制浏览器全屏)

javascript实现浏览器全屏显示和退出全屏代码(js控制浏览器全屏)

浏览器内置全屏浏览网页的功能,通过键盘快捷键F11可以进入全屏模式,而在网页端则可以通过js代码使用requestFullScreen()方法进入浏览器全屏浏览模式,使用exitFullScreen...

CSS修改表单输入框placeholder属性文字颜色(input中placeholder改变字体颜色)

CSS修改表单输入框placeholder属性文字颜色(input中placeholder改变字体颜色)

placeholer是HTML5新增属性,规定可描述输入字段预期值的简短的提示信息,IE10+、Firefox、Opera、Chrome 和 Safari 浏览器支持该属性。 针对不同浏览器修...

最好用的自定义滚动条样式jquery插件mCustomScrollbar(jquery设置滚动条位置)

最好用的自定义滚动条样式jquery插件mCustomScrollbar(jquery设置滚动条位置)

通过jquery滚动条插件mCustomScrollbar.js可以自定义滚动动条CSS样式和滚动条的位置,支持垂直和水平两个方向的滚动条,支持jQuery mousewheel plugin插件的...

解决HTML5标签video视频不能播放,显示无效源的问题(html5 video 不能自动播放)

解决HTML5标签video视频不能播放,显示无效源的问题(html5 video 不能自动播放)

视频本地播放器可以打开播放,在网页上使用video标签不能播放或显示无效源,原因是视频的编码不被video支持,解决方法是转换视频编码。 当前video标签支持Ogg、MPEG4(mp4)、W...