LintCode 堆化详解及实例代码

LintCode 堆化详解及实例代码

给出一个整数数组，堆化操作就是把它变成一个最小堆数组。

对于堆数组A，A[0]是堆的根，并对于每个A[i]，A [i * 2 + 1]是A[i]的左儿子并且A[i * 2 + 2]是A[i]的右儿子。

样例

给出 [3,2,1,4,5]，返回[1,2,3,4,5] 或者任何一个合法的堆数组

挑战

O(n)的时间复杂度完成堆化

说明

什么是堆？

堆是一种数据结构，它通常有三种方法：push， pop 和 top。其中，“push”添加新的元素进入堆，“pop”删除堆中最小/最大元素，“top”返回堆中最小/最大元素。

什么是堆化？

把一个无序整数数组变成一个堆数组。如果是最小堆，每个元素A[i]，我们将得到A[i * 2 + 1] >= A[i]和A[i  * 2 + 2] >= A[i]
如果有很多种堆化的结果？

返回其中任何一个。

分析：一开始想到堆化么肯定就是堆排序吧，粗粗一想貌似复杂度是O(nlgn)，后来参考该文章才知道O(nlgn)是复杂度上限，平均是O(n)

代码：

class Solution {
public:
  /**
   * @param A: Given an integer array
   * @return: void
   */
  void heapify(vector<int> &A) {
    // write your code here
    int n = A.size()-1;
    for(int i=n/2;i>=0;i--)
      heapify(A,i);
  }
  void heapify(vector<int> &A,int i)
  {
    int l = 2*i+1;
    int r = 2*i+2;
    int smallest = i;
    if(l<A.size()&&A[l]<A[smallest])
      smallest = l;
    if(r<A.size()&&A[r]<A[smallest])
      smallest = r;
    if(smallest!=i)
    {
      swap(A[i],A[smallest]);
      heapify(A,smallest);
    }
  }
};

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

赞 (0)

相关推荐

  • LintCode-排序列表转换为二分查找树分析及实例

    给出一个所有元素以升序排序的单链表,将它转换成一棵高度平衡的二分查找树 您在真实的面试中是否遇到过这个题? 分析:就是一个简单的递归,只是需要有些链表的操作而已 代码: /** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } * Defin

  • LintCode 堆化详解及实例代码

    LintCode 堆化详解及实例代码 给出一个整数数组,堆化操作就是把它变成一个最小堆数组. 对于堆数组A,A[0]是堆的根,并对于每个A[i],A [i * 2 + 1]是A[i]的左儿子并且A[i * 2 + 2]是A[i]的右儿子. 样例 给出 [3,2,1,4,5],返回[1,2,3,4,5] 或者任何一个合法的堆数组 挑战 O(n)的时间复杂度完成堆化 说明 什么是堆? 堆是一种数据结构,它通常有三种方法:push, pop 和 top.其中,"push"添加新的元素进入堆,

  • MyBatis获取数据库自生成的主键Id详解及实例代码

    MyBatis获取数据库自生成的主键Id详解及实例代码 在使用MySQL数据库时我们一般使用数据库的自增主键自动产生主键.如果在插入主表时,我们需要同时插入从表的数据,这时我们通常需要知道主表插入时自动产生的主键Id值. 下面介绍使用MyBatis进行插入时,如何同时获取数据库自生成的主键: 1.XML配置文件 <insert id="insert" parameterType="Person" useGeneratedKeys="true"

  • MySQL 序列 AUTO_INCREMENT详解及实例代码

    MySQL 序列 AUTO_INCREMENT详解及实例代码 MySQL序列是一组整数:1, 2, 3, ...,由于一张数据表只能有一个字段自增主键, 如果你想实现其他字段也实现自动增加,就可以使用MySQL序列来实现. 本章我们将介绍如何使用MySQL的序列. 使用AUTO_INCREMENT MySQL中最简单使用序列的方法就是使用 MySQL AUTO_INCREMENT 来定义列. 实例 以下实例中创建了数据表insect, insect中id无需指定值可实现自动增长. mysql>

  • Java 两种延时thread和timer详解及实例代码

    Java 两种延时thread和timer详解及实例代码 在Java中有时候需要使程序暂停一点时间,称为延时.普通延时用Thread.sleep(int)方法,这很简单.它将当前线程挂起指定的毫秒数.如 try { Thread.currentThread().sleep(1000);//毫秒 } catch(Exception e){} 在这里需要解释一下线程沉睡的时间.sleep()方法并不能够让程序"严格"的沉睡指定的时间.例如当使用5000作为sleep()方法的参数时,线 程

  • Spring组件自动扫描详解及实例代码

    Spring组件自动扫描详解及实例代码 问题描述 一个系统往往有成千上万的组件,如果需要手动将所有组件都纳入spring容器中管理,是一个浩大的工程. 解决方案 Spring 提供组件扫描(component scanning)功能.它能从classpath里自动扫描.侦测和实例化具有特定注解的组件.基本的注解是@Component,它标识一个受Spring管理的组件.其他特定的注解有@Repository.@Service和@Controller,它们分别标识了持久层.服务处和表现层的组件.

  • Java中自定义异常详解及实例代码

    Java中自定义异常详解及实例代码 下面做了归纳总结,欢迎批评指正 自定义异常 class ChushulingException extends Exception { public ChushulingException(String msg) { super(msg); } } class ChushufuException extends Exception { public ChushufuException(String msg) { super(msg); } } 自定义异常 En

  • Spring AOP 基于注解详解及实例代码

    Spring AOP  基于注解详解及实例代码 1.启用spring对@AspectJ注解的支持: <beans xmlns:aop="http://www.springframework.org/schema/aop"...> <!--启动支持--> <aop:aspectj-autoproxy /> </beans> 也可以配置AnnotationAwareAspectJAutoProxyCreator Bean来启动Spring对@

  • java多线程编程技术详解和实例代码

     java多线程编程技术详解和实例代码 1.   Java和他的API都可以使用并发. 可以指定程序包含不同的执行线程,每个线程都具有自己的方法调用堆栈和程序计数器,使得线程在与其他线程并发地执行能够共享程序范围内的资源,比如共享内存,这种能力被称为多线程编程(multithreading),在核心的C和C++语言中并不具备这种能力,尽管他们影响了JAVA的设计. 2.   线程的生命周期 新线程的生命周期从"新生"状态开始.程序启动线程前,线程一直是"新生"状态:

  • JS 实现计算器详解及实例代码（一）

    JS 实现计算器详解及实例代码（一）

    Javascript 实现计算器: 系列文章: JS 实现计算器详解及实例代码(一) Javascript 实现计算器时间功能详解及实例(二) 小型JavaScript计算器 自己寻思出的解决方案,比较笨拙的方法,虽然完成了但是还有不少bug,用的方法也不是最有效的,基本功能算是完成了,一些小的细节地方也考虑到了,但是还有其他的细节需要处理. 总体设计思路是,先画草图 -> 设计UI -> 编写UI代码 -> 编写CSS -> 编写JS逻辑代码: 面板(main-board) 面板

  • java 单播、广播、组播详解及实例代码

    java 单播.广播.组播详解及实例代码 在当前网络通信中(TCP/IP也不例外)有三种通信模式:单播.广播.组播(又叫多播, 个人感觉叫多播描述的有点不恰当),其中多播出现的时间最晚,但同时具备单播和广播的优点,最具有发展前景. 一.通信方式分类: 1.单播:单台主机与单台主机之间的通信: 2.广播:单台主机与网络中所有主机的通信: 3.组播:单台主机与选定的一组主机的通信: 二.单播:    单播是网络通信中最常见的,网络节点之间的通信 就好像是人们之间的对话一样.如果一个人对另外一个人说话

随机推荐