文档章节

堆排序

AllenOR灵感
 AllenOR灵感
发布于 2017/09/10 01:00
字数 257
阅读 0
收藏 0

二叉堆的定义:二叉堆是一组能够用堆有序的完全二叉树排序的元素,并在数组中按照层级储存(不使用数组的第一个元素)。
堆有序:一课二叉树的每个节点都大于等于他的两个子节点
完全二叉树:除了最后一层外的其他每一层都 都被完全填充,最后一层向左对齐。

一图胜千言:

一个二叉堆数组
一个二叉堆数组
//这里的数组是从1开始排列的
    public void sort(Comparable[] a) {
        int n = a.length;
        for (int k = n / 2; k >= 1; k--) {
            sink(a, k, n);
        }
        while (n > 1) {
            exch(a, 1, n--);
            sink(a, 1, n);
        }
    }

    private void sink(Comparable[] a, int k, int n) {
        while (2 * k <= n) {
            int j = 2 * k;
            if (j < n && less(a, j, j + 1))
                j++;
            if (!less(a, k, j))
                break;
            exch(a, k, j);
            k = j;
        }
    }

    private boolean less(Comparable[] a, int i, int j) {
        return a[i - 1].compareTo(a[j - 1]) < 0;
    }

    private void exch(Object[] a, int i, int j) {
        Object temp = a[i - 1];
        a[i - 1] = a[j - 1];
        a[j - 1] = temp;
    }

方法解读在优先队列

本文转载自:http://www.jianshu.com/p/49f44d464d8c

上一篇: 二叉查找树
下一篇: 二分查找
AllenOR灵感
粉丝 11
博文 2635
码字总数 83001
作品 0
程序员
私信 提问

暂无文章

正则表达式匹配

请实现一个函数用来匹配包括 '.' 和 '*' 的正则表达式。模式中的字符 '.' 表示任意一个字符,而 '*' 表示它前面的字符可以出现任意次(包含 0 次)。 在本题中,匹配是指字符串的所有字符匹配...

Garphy
51分钟前
5
0
Laravel 5.1的多路由文件的配置

默认的路由配置文件只有一个, \app\Http\routes.php。 在同一个文件中写路由容易起冲突,文件会越来越大,就需要定义多个路由文件。 找到加载\app\Http\routes.php的文件, 打开\app\Provid...

mdoo
今天
5
0
Hibernate 5 开始使用指南前言

同时在面向对象软件和关系型数据库进行工作,可能会非常复杂和费时。数据在对象和数据库之间可能会不一致,然后导致开发成本会非常高。 Hibernate 是一个针对 Java 环境的对象关系映射(Obj...

honeymoose
今天
6
0
聊聊nacos ServiceManager的UpdatedServiceProcessor

序 本文主要研究一下nacos ServiceManager的UpdatedServiceProcessor ServiceManager.init nacos-1.1.3/naming/src/main/java/com/alibaba/nacos/naming/core/ServiceManager.java @Compone......

go4it
今天
7
0
正则表达式的使用(QQ格式的判断与空格的切割)

//正则表达式的使用 public static void main(String[] args) throws IOException, ClassNotFoundException { //test1("123456"); test2("-1 99 kk"); } /** * ......

zhengzhixiang
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部