文档章节

最小堆的构建和排序

zongjh
 zongjh
发布于 2017/05/10 17:34
字数 698
阅读 58
收藏 0

最近在研究寻找最大的K个数,里面提到了利用最小堆,所以就顺便了解了一下。

package com.xylx.utils.selectK;

import com.xylx.utils.GsonUtils;

/**
 * Created by zongjh on 17-5-10.
 */
public class MinHeap {
    public static void main(String[] args) {
        int[] arr = {2,6,3,9,4,8};
        buildMinHeap(arr);
        System.out.println(GsonUtils.getJsonFromObject(arr));
        change(5, arr);
        System.out.println(GsonUtils.getJsonFromObject(arr));

        change(4, arr);
        System.out.println(GsonUtils.getJsonFromObject(arr));
    }

    /**
     * 都建构建最小堆
     * @param arr
     */
    public static void buildMinHeap(int[] arr) {
        for (int i=0; i<arr.length; i++) {
            handleMinHeap(arr, arr.length, i); //从前向后构建最小堆
        }
    }

    /**
     * 检查value是否比arr[0]大,如果大于,则对堆进行重构
     * @param value
     * @param arr
     */
    public static void change(int value, int[] arr) {
        if (value > arr[0]) {
            arr[0] = value;
            handleMinHeap(arr, arr.length, 0);
        }
    }

    /**
     * 最小堆排序
     * @param arr
     */
    public static void minHeapSort(int[] arr) {
        for (int i=arr.length-1; i>0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            handleMinHeap(arr, i, 0);
        }
    }

    /**
     * 节点转换
     * @param arr
     * @param heapSize
     * @param current
     */
    public static void handleMinHeap(int[] arr, int heapSize, int current) {
        int leftChildIndex = getLeftChiledIndex(current);
        int rightChildIndex = getRightChildIndex(current);
        int minIndex = current; //找到三个节点中最小的那个
        if (leftChildIndex<heapSize && arr[current] > arr[leftChildIndex]) {
            minIndex = leftChildIndex;
        }
        if (rightChildIndex<heapSize && arr[minIndex] > arr[rightChildIndex]) {
            minIndex = rightChildIndex;
        }
        if (minIndex != current) {
            int tmp = arr[current]; //将最小的值转移到父节点位置,这样可能会破坏原先子节点的结果,所以需要递归
            arr[current] = arr[minIndex];
            arr[minIndex] = tmp;
            handleMinHeap(arr, heapSize, minIndex);
        }
    }

    /**
     * 获取左孩子节点位置
     * @param current
     * @return
     */
    public static int getLeftChiledIndex(int current) {
        return (current<<1) + 1;
    }

    /**
     * 获取右孩子节点位置
     * @param current
     * @return
     */
    public static int getRightChildIndex(int current) {
        return (current<<1) + 2;
    }

    /**
     * 获取父节点位置
     * @param current
     * @return
     */
    public static int getParentIndex(int current) {
        return (current-1)>>1;
    }
}

下面是一个辅助类:主要用于数据生成和打印。

package com.xylx.utils.selectK;

import java.util.Arrays;
import java.util.Random;

/**
 * Created by zongjh on 17-5-6.
 */
public class Constans {

    private static int JI_ZHUN = 100;
    public static int K = 10;

    /**
     * 生成长度为length的int类型数组
     * @param length
     * @return
     * @throws Exception
     */
    public static int[] getLengthArr(int length) {
        if (length<1) {
            length = 100;
        }
        int[] arr = new int[length];
        int[] yzArr = new int[length];
        Random random = new Random();
        for (int i=0; i<length; i++) {
            arr[i] = random.nextInt(JI_ZHUN);
            yzArr[i] = arr[i];
        }
        System.out.println("参加排序前,使用Java自带函数排序,结果为:");
        System.out.println("==========================================");
        Arrays.sort(yzArr);
        for (int i=0; i<yzArr.length; i++) {
            System.out.print(yzArr[i]+"    ");
        }
        System.out.println("\n==========================================");
        System.out.println();
        return arr;
    }

    public static void printArr(int[] arr) {
        System.out.println("数组输出:");
        for (int i=0; i<arr.length; i++) {
            System.out.print(arr[i]+"    ");
        }

        System.out.println();
    }

    /**
     * 校验排序是否正确
     * @param arr
     * @return
     */
    public static boolean isOk(int[] arr) {
        for (int i=0; i<arr.length-1; i++) {
            if (arr[i+1] < arr[i]) {
                return false;
            }
        }
        return true;
    }

    public static void selectK(int[] arr) {
        System.out.println("最大的K个数:");
        for (int i=arr.length-K; i<arr.length; i++) {
            System.out.print(arr[i]+"    ");
        }
        System.out.println();
    }
}

关于一个节点其父节点和字节的位置可以参考以下说法:

如果下标从0开始:

    父节点=(i-1)/2

    左子节点:2*i + 1

    右子节点:2*i + 2

 

如果下标从1开始

    父节点:i/2

    左子节点:2*i

    右子节点: 2*i + 1

喜欢聊技术或者聊观点,可以加入公号:【花生读书汇】

一起:励志,成长,学习,分享。

【花生读书汇】

© 著作权归作者所有

zongjh
粉丝 1
博文 39
码字总数 12405
作品 0
东城
程序员
私信 提问
JavaScript数据结构与算法(堆)

堆是一种完全二叉树. 堆得使用基本是通过最大堆和最小堆来实现的! 最大堆,最大堆中的最大元素值出现在根结点(堆顶),堆中每个父节点的元素值都大于等于其孩子结点 最小堆,最小堆中的最大元...

fiveoneLei
2018/07/12
0
0
priorityQueue 堆

priorityQueue 通过add方法添加,通过poll方法一次获得一个最小元素(元素需要实现Comparable或提供Comparator的实现类),实现原理最小堆,也就是说元素按照最小堆结构存放。 最小堆是一个完...

hgqxjj
2017/11/22
0
0
算法与数据结构(四)堆排序:优先队列实现

堆排序 排序次要的,接触新的数据结构;堆 堆和优先队列 Heap and Priority Queue 什么是优先队列? 普通队列:先进先出;后进后出 优先队列:出队顺序和入队顺序无关;和优先级相关 为什么使...

天涯明月笙
2017/09/16
0
0
[剑指offer] 数据流中的中位数

本文首发于我的个人博客:尾尾部落 题目描述 如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,...

繁著
2018/07/26
0
0
经典排序算法(Java实现)

以下程序均将数据封装于DataWrap数据包装类中,如下所示: 三、插入排序 1、直接插入排序   每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列中的适当位置,直到全部记...

whc20011
2016/02/02
37
0

没有更多内容

加载失败,请刷新页面

加载更多

Mybatis Plus删除

/** @author beth @data 2019-10-17 00:30 */ @RunWith(SpringRunner.class) @SpringBootTest public class DeleteTest { @Autowired private UserInfoMapper userInfoMapper; /** 根据id删除......

一个yuanbeth
今天
4
0
总结

一、设计模式 简单工厂:一个简单而且比较杂的工厂,可以创建任何对象给你 复杂工厂:先创建一种基础类型的工厂接口,然后各自集成实现这个接口,但是每个工厂都是这个基础类的扩展分类,spr...

BobwithB
今天
5
0
java内存模型

前言 Java作为一种面向对象的,跨平台语言,其对象、内存等一直是比较难的知识点。而且很多概念的名称看起来又那么相似,很多人会傻傻分不清楚。比如本文我们要讨论的JVM内存结构、Java内存模...

ls_cherish
今天
4
0
友元函数强制转换

友元函数强制转换 p522

天王盖地虎626
昨天
5
0
js中实现页面跳转(返回前一页、后一页)

本文转载于:专业的前端网站➸js中实现页面跳转(返回前一页、后一页) 一:JS 重载页面,本地刷新,返回上一页 复制代码代码如下: <a href="javascript:history.go(-1)">返回上一页</a> <a h...

前端老手
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部