lintcode: 堆化
2024-09-09 00:40:46
堆化
给出一个整数数组,堆化操作就是把它变成一个最小堆数组。
对于堆数组A,A[0]是堆的根,并对于每个A[i],A [i * 2 + 1]是A[i]的左儿子并且A[i * 2 + 2]是A[i]的右儿子。
说明
什么是堆?
- 堆是一种数据结构,它通常有三种方法:push, pop 和 top。其中,“push”添加新的元素进入堆,“pop”删除堆中最小/最大元素,“top”返回堆中最小/最大元素。
什么是堆化?
- 把一个无序整数数组变成一个堆数组。如果是最小堆,每个元素A[i],我们将得到A[i * 2 + 1] >= A[i]和A[i * 2 + 2] >= A[i]
如果有很多种堆化的结果?
- 返回其中任何一个
给出 [3,2,1,4,5]
,返回[1,2,3,4,5]
或者任何一个合法的堆数组
解题
根据给的样例,直接排序后就符合答案。
public class Solution {
/**
* @param A: Given an integer array
* @return: void
*/
public void heapify(int[] A) {
// write your code here
Arrays.sort(A);
}
}
递归进行堆排序
public class Solution {
/**
* @param A: Given an integer array
* @return: void
*/
public void heapify(int[] A) {
// write your code here
for(int i = (A.length - 1)/2;i>=0;i--)
heapify(A,i);
}
public void heapify(int[] A,int i){
int l = 2*i + 1;
int r = 2*i + 2;
int smallest = i;
if(l < A.length && A[l] < A[smallest])
smallest = l;
if( r < A.length && A[r] < A[smallest])
smallest = r;
if(smallest!=i){
int tmp = A[i];
A[i] = A[smallest];
A[smallest] = tmp;
heapify(A,smallest);
}
}
}
最新文章
- python SimpleHTTPRequestHandler初探
- linux系统基础网络配置
- JS 中对象的简单创建和继承
- NOIP200406合并果子
- HTML目录
- 【转】VC++消息钩子编程
- Ⅲ.AngularJS的点点滴滴-- 路由
- QQ 群也能接收告警啦!团队沟通力 Up Up!
- JSON.parse(),JSON.stringify(),jQuery.parseJSON()的用法
- Java它配备了一个很好的工具2
- linuxlab下虚拟板与主机通信
- windows server,nginx安装,配置,运行nodeJS后端的web项目的实现,以及错误分析及解决方法
- 防F12审查元素扒代码:按下F12关闭当前页面
- LeetCode之“链表”:Merge Two Sorted Lists &;&; Merge k Sorted Lists
- CDH简易离线部署文档
- Nginx禁止IP直接访问网站
- C# - 设计模式 - 策略模式
- Win32汇编学习(5):绘制文本2
- json为txt文本加密
- POJ 2379
热门文章
- (转)redis 学习笔记(1)-编译、启动、停止
- c# 各种排序算法+找第二大的数+句子单词反转
- 如何写一个简单的Web Server(一)
- java读取资源文件
- Shade勒索病毒 中敲诈病毒解密 如 issbakev9_Data.MDF.id-A1E.f_tactics@aol.com.xtbl 解决方法
- c语言学习strcopy
- c++ 缺少动态库
- 浅谈自我对git的初步认识
- HDU 5564 Clarke and digits 状压dp+矩阵加速
- printf的一个常用技巧