文档章节

堆的时间复杂度

o
 osc_1ee7cxmx
发布于 2018/08/06 19:34
字数 445
阅读 7
收藏 0

精选30+云产品,助力企业轻松上云!>>>

构建堆的过程,O(N)

从下面的元素向下沉

package sortdemo;

import java.util.Arrays;

/**
 * Created by chengxiao on 2016/12/17.
 * 堆排序demo
 */
public class HeapSort {
    public static void main(String []args){
        int []arr = {9,8,7,6,5,4,3,2,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int []arr){
        //1.构建大顶堆
        for(int i=arr.length/2-1;i>=0;i--){
            //从第一个非叶子结点从下至上,从右至左调整结构
            adjustHeap(arr,i,arr.length);
        }
        //2.调整堆结构+交换堆顶元素与末尾元素
        for(int j=arr.length-1;j>0;j--){
            swap(arr,0,j);//将堆顶元素与末尾元素进行交换
            adjustHeap(arr,0,j);//重新对堆进行调整
        }

    }

    /**
     * 调整大顶堆(仅是调整过程,建立在大顶堆已构建的基础上)
     * @param arr
     * @param i
     * @param length
     */
    public static void adjustHeap(int []arr,int i,int length){
        int temp = arr[i];//先取出当前元素i
        for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始,也就是2i+1处开始
            if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点,k指向右子结点
                k++;
            }
            if(arr[k] >temp){//如果子节点大于父节点,将子节点值赋给父节点(不用进行交换)
                arr[i] = arr[k];
                i = k;
            }else{
                break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }

    /**
     * 交换元素
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int []arr,int a ,int b){
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

堆排序,每次交换堆顶的元素和结尾的元素,调整堆,每次O(logN)

堆插入,push_heap每次将元素放在结尾,将结尾元素向上查找更大或更小的元素下沉,每次O(logN)

堆删除,pop_heap,删除堆顶元素,将堆顶元素放在结尾等待删除,将剩下的元素重建建堆。

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
数据结构(堆)

定义: 数据结构中的堆是一种特殊的二叉树。 堆 必须符合以下两个条件: 是一棵完全二叉树。 任意一个节点的值都大于(或小于)左右子节点的值。 从第一点可以知道,堆适合用数组来存储。 第...

潦草的犀牛
2019/12/14
11
0
【LeetCode题解】347_前K个高频元素(Top-K-Frequent-Elements)

更多 LeetCode 题解笔记可以访问我的 github。 [TOC] 描述 给定一个非空的整数数组,返回其中出现频率前 k 高的元素。 示例 1: 示例 2: 说明: 你可以假设给定的 k 总是合理的,且 1 ≤ k ≤...

osc_eiwgrws6
2018/11/13
6
0
七大内排序

我们更加排序记录是否全部放置在内存中,将排序分为内排序和外排序,这里我们主要了解七个经典的内排序:插入排序,希尔排序,选择排序,堆排序,冒泡排序,快速排序,归并排序。 对于一个问...

osc_8ik0jlpr
2018/02/27
2
0
python--8大排序(原理+代码)

常用的排序方法:冒泡排序、选择排序、插入排序、快速排序、堆排序、归并排序 冒泡排序(Bubble Sort):   比较相邻的元素。如果第一个比第二个大(升序),就交换他们两个。   对每一对相...

osc_e3fen7cx
2019/07/19
5
0
JavaScript数据结构与算法(排序算法)

比较排序算法一般有三个指标 时间复杂度, 算法执行完成所需要的时间 空间复杂度, 算法执行完成所需要的空间 稳定性,当二个元素的值相同的时候,排序之后二个元素的前后位置是否发生改变 ...

fiveoneLei
2018/07/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Eclipse_JavaEE_Tomcat_MySQL环境配置

安装java环境,配置系统变量(JAVA_HOME,绝对路径) 下载eclipse+Tomcat+mysql window——》preference——》server——》runtime——》tomcat环境 项目右键build path 配mysql jar ,libra...

愿有时光可回首
57分钟前
20
0
MySQL原理 - InnoDB引擎 - 行记录存储 - Redundant行格式

本文基于 MySQL 8 在上一篇:MySQL原理 - InnoDB引擎 - 行记录存储 - Compact格式 中,我们介绍了什么是 InnoDB 行记录存储以及 Compact 行格式,在这一篇中,我们继续介绍其他三种行格式。 ...

zhxhash
今天
29
0
leetcode面试题 17.13(恢复空格)--Java语言实现

求: 哦,不!你不小心把一个长篇文章中的空格、标点都删掉了,并且大写也弄成了小写。像句子"I reset the computer. It still didn’t boot!"已经变成了"iresetthecomputeritstilldidntboo...

拓拔北海
今天
19
0
B站跨年晚会究竟做对了什么?

燃财经(ID:rancaijing)原创 作者 | 赵磊 编辑 | 周昶帆 “补课”是《bilibili晚会 二零一九最美的夜》这个视频中,观众在前两分钟刷得最多的弹幕,寓意着观众是在元旦之后回来补看跨年晚会...

子乾建建_Jeff
01/07
59
0
关于Scrapy爬虫项目运行和调试的小技巧(上篇)

点击上方“Python爬虫与数据挖掘”,进行关注 回复“书籍”即可获赠Python从入门到进阶共10本电子书 今 日 鸡 汤 迟日江山丽,春风花草香。泥融飞燕子,沙暖睡鸳鸯。 扫除运行Scrapy爬虫程序...

yuhan336
04/02
26
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部