LintCode 堆化代码

给出一个整数数组,堆化操作就是把它变成一个最小堆数组。 对于堆数组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
     */
    private void siftdown(int[] A, int k) {
        while (k < A.length) {
            int smallest = k;
            if (k * 2 + 1 < A.length && A[k * 2 + 1] < A[smallest]) {
                smallest = k * 2 + 1;
            }
            if (k * 2 + 2 < A.length && A[k * 2 + 2] < A[smallest]) {
                smallest = k * 2 + 2;
            }
            if (smallest == k) {
                break;
            }
            int temp = A[smallest];
            A[smallest] = A[k];
            A[k] = temp;
            
            k = smallest;
        }
    }
    
    public void heapify(int[] A) {
        for (int i = A.length / 2; i >= 0; i--) {
            siftdown(A, i);
        } 
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏用户画像

剑指offer 栈的压入,弹出序列

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序...

873
来自专栏积累沉淀

必须掌握的八种排序(3-4)--简单选择排序,堆排序

3、简单选择排序 (1)基本思想:在要排序的一组数中,选出最小的一个数与第一个位置的数交换; 然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第...

2149
来自专栏Java编程

Java List 用法代码分析(非常详细)

Java中可变数组的原理就是不断的创建新的数组,将原数组加到新的数组中,下文对Java List用法做了详解。

5311
来自专栏机器学习从入门到成神

Java之使用增强for循环和迭代器遍历

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

1711
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——LinkedHashMap

994
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——LinkedList

32012
来自专栏赵俊的Java专栏

不用加减乘除做加法

1734
来自专栏架构之路

Java 集合系列02之 Collection架构

概要 首先,我们对Collection进行说明。下面先看看Collection的一些框架类的关系图: ? Collection是一个接口,它主要的两个分支是:L...

3574
来自专栏Java学习网

Java实现的一个简单计算器,有字符分析功能

需求:实现一个简单的计算器来分析一个简单的表达式字符串。 表达式字符串可能包含括号,+ +或减号,非负整数和空格。 例子:“1 + 1 = 2,(1)“= 1(...

3345
来自专栏郭耀华‘s Blog

Java集合框架(三)—— List、ArrayList、Vector、Stack

List接口 List集合代表一个有序集合,集合中每一个元素都有其对应的顺序索引。List集合容许使用重复元素,可以通过索引来访问指定位置的集合对象。 ...

3095

扫码关注云+社区

领取腾讯云代金券