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);
}
}
};
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
-
本文向大家介绍AngularJS 模块化详解及实例代码，包括了AngularJS 模块化详解及实例代码的使用技巧和注意事项，需要的朋友参考一下 AngularJS有几大特性，比如： 1 MVC 2 模块化 3 指令系统 4 双向数据绑定 那么本篇就来看看AngularJS的模块化。 首先先说一下为什么要实现模块化： 1 增加了模块的可重用性 2 通过定义模块，实现加载顺
-
本文向大家介绍Java中初始化块详解及实例代码，包括了Java中初始化块详解及实例代码的使用技巧和注意事项，需要的朋友参考一下 Java中初始化块详解 在Java中,有两种初始化块:静态初始化块和非静态初始化块. 静态初始化块:使用static定义,当类装载到系统时执行一次.若在静态初始化块中想初始化变量,那仅能初始化类变量,即static修饰的数据成员. 非静态初始化块:在每个对象生成时都会被执
-
本文向大家介绍Java Annotation详解及实例代码，包括了Java Annotation详解及实例代码的使用技巧和注意事项，需要的朋友参考一下 一、Annotation简介 从Java1.5开始，Java增加了元数据（MetaData）的支持，也就是Annotation（注释）； Annotation能被用来为程序元素（类、方法、成员变量等）设置元数据； Annotation不能影响程序代
-
本文向大家介绍java HashMap详解及实例代码，包括了java HashMap详解及实例代码的使用技巧和注意事项，需要的朋友参考一下 java HashMap Map集合的遍历 方式1，根据键查询值 获取所有键的集合 遍历键的集合，获取每一个键 根据键，查询值 方式2，根据键值对的对象查询键和值 获取所有键值对的对象的集合 遍历键值对的对象的集合，获取到每一个键值对的对象 根据键值对的对象
-
本文向大家介绍ReactNative Alert详解及实例代码，包括了ReactNative Alert详解及实例代码的使用技巧和注意事项，需要的朋友参考一下 Alert顾名思义一就是一个警告框，一般使用情况比如：退出登录，清楚缓存，提示修改密码等等。。。ReactNative中的Alert只有一个静态方法alert()其中有四个参数：标题，信息，按钮和按钮类型 在Android按钮至多有三个 下
-
本文向大家介绍Angularjs CURD 详解及实例代码，包括了Angularjs CURD 详解及实例代码的使用技巧和注意事项，需要的朋友参考一下 Angularjs CURD 前言 基于一个手机端的项目使用了angularjs，硬着头皮去用，有很多的疑问还需要一一去验证，刚开始总是感觉找不到北，总是感觉有很多概念，而且似乎ng既夹杂MVC又夹杂MVVM的思想， 忙里偷闲敲了个简