用自行实现的优先队列进行四字成语汉字频率统计

文章目录

        • 背景
        • 构建最大堆
          • 代码实现
          • 测试
        • 通过最大堆实现优先队列
        • 成语汉字频率统计案例
          • 统计四字成语文件中的汉字出现频率的前5位
          • 项目结构
          • 汉字频率的类
          • 优先队列测试类
          • 成语汉字统计主程序

背景

在《自已做动画及编写程序搞清楚最大堆的实现原理》这篇文章中,我们通过动图分析编 码自行实现了最大堆的数据结构,并在文章末尾提到了最大堆的应用–优先队列。该文将通过“四字成语汉字频率统计”的实际应用,把最大堆与优先队列的原理再次进行深入剖析。

构建最大堆

  • 由于堆是一种特殊的完全二叉树,可以利用数组集合形成线性存储的数据结构。
  • 通过每个父结点与左右子结点大小的比较,使得根结点最大,且每个父结点都大于左右结点。
    在这里插入图片描述
代码实现
/**
 * 最大堆的底层实现
 *
 * @author zhuhuix
 * @date 2020-06-28
 * @date 2020-07-01 通过数组构建最大堆
 */
public class MaxHeap<E extends Comparable<E>> {

    // 存放元素的数组集合
    private ArrayList<E> list;

    MaxHeap() {
        this.list = new ArrayList<>();
    }


    // 得到左孩子索引
    private int getLeftChildIndex(int i) {
        return (2 * i + 1);
    }

    // 得到右孩子索引
    private int getRightChildIndex(int i) {
        return (2 * i + 2);
    }

    // 得到父结点索引
    private int getParentIndex(int i) {
        if (i == 0) {
            throw new IllegalArgumentException("非法索引值");
        } else {
            return ((i - 1) / 2);
        }
    }

    // 通过数组创建最大堆
    public void heapify(E[] arr){
        this.list.addAll(Arrays.asList(arr));
        for (int i=getParentIndex(this.list.size()-1);i>=0;i--){
            shiftDown(i);
        }
    }

    // 添加元素
    public void add(E e) {
        this.list.add(e);
        /**
         * 将加入的结点与父结点进行比较:
         * 如果加入的结点大于父结点,则进行上浮
         * 直至新结点小于或等于父结点为止
         */
        shiftUp(this.list.size() - 1);
    }

    // 元素上浮
    private void shiftUp(int i){
        while (i > 0) {
            E current = this.list.get(i);
            E parent = this.list.get(getParentIndex(i));
            // 如果父结点元素大于当前加入的元素,则进行交换
            if (parent.compareTo(current) < 0) {
                // 交换新加入的结点与父结点的位置
                Collections.swap(this.list, i, getParentIndex(i));
            } else {
                break;
            }
            i = getParentIndex(i);
        }
    }


    // 查找最大元素
    public E findMax() {
        if (this.list.size() == 0) {
            return null;
        }
        // 最大堆中的元素永远在根结点
        return this.list.get(0);
    }

    // 取出最大元素
    public E getMax() {
        if (findMax() != null) {
            E e = findMax();

            /**
             * 取出最大元素后,需要把堆中第二大的元素放置在根结点:
             * 将根结点元素与最后面的元素进行交换,
             * 让最后面的元素出现在根结点,并移除最大元素
             * 将根结点的元素与左右孩子结点比较,直至根结点的元素变成最大值
             */
            int i = 0;
            Collections.swap(this.list, i, this.list.size() - 1);
            this.list.remove(this.list.size() - 1);
            shiftDown(i);

            return e;
        } else {
            return null;
        }
    }

    // 元素下沉
    private void shiftDown(int i){
        // 通过循环进行当前结点与左右孩子结点的大小比较
        while (getLeftChildIndex(i) < this.list.size()) {
            int leftIndex = getLeftChildIndex(i);

            // 通过比较左右孩子的元素哪个较大,确定当前结点与哪个孩子进行交换
            int index = leftIndex;
            if (getRightChildIndex(i) < this.list.size() &&
                    this.list.get(getRightChildIndex(i)).compareTo(this.list.get(leftIndex)) > 0) {
                index = getRightChildIndex(i);
            }
            // 如果当前结点都大于左右孩子,则结束比较
            if (this.list.get(i).compareTo(this.list.get(index)) >= 0) {
                break;
            }

            Collections.swap(this.list, i, index);
            i = index;
        }
    }

    // 返回最大堆中的元素个数
    public int getSize(){
        return this.list.size();
    }

    // 用元素取代最大堆中的最大元素
    public E replace(E e){
        // 暂存最大元素
        E ret= findMax();
        // 将最大元素的位置放入要取代的元素
        this.list.set(0,e);
        // 通过下浮操作形成最大堆
        shiftDown(0);
        return ret;
    }
}

测试
/**
 * 最大堆的底层实现--测试程序
 *  * @author zhuhuix
 * @date 2020-07-01
 */
public class MaxHeapTest {
    public static void main(String[] args) {
        MaxHeap<Integer> maxHeap = new MaxHeap<>();

        // 将10个数字加入形成最大堆
        Integer[] arrays = {19,29,4,2,27,0,38,15,12,31};
        maxHeap.heapify(arrays);

        // 依次从堆中取出最大值
        for (int i = 0; i < arrays.length; i++) {
            System.out.println("第"+(i+1)+"次取出堆目前的最大值:"+maxHeap.getMax());
        }
    }
}

在这里插入图片描述

通过最大堆实现优先队列

  • 具有优先级最高的元素最先出队。
/**
 * 用最大堆的数据结构实现优先队列
 *
 * @author zhuhuix
 * @date 2020-07-01
 */
public class PriorityQueue<E extends Comparable<E>> {
    private MaxHeap<E> mhp;

    PriorityQueue() {
        mhp = new MaxHeap<>();
    }

    // 入队
    public void enqueue(E e) {
        mhp.add(e);
    }

    // 优选级最高的元素出队
    public E dequeue() {
        return mhp.getMax();
    }

    // 查看优先级最高的元素
    public E getFront() {
        return mhp.findMax();
    }

    // 队列元素个数
    public int getSize() {
        return mhp.getSize();
    }
}

成语汉字频率统计案例

统计四字成语文件中的汉字出现频率的前5位
  • 通过最大堆的数据结构实现优先队列,优先队列具有入队、出队、查看最先出队元素的功能;
  • 建立一个汉字频率的类,并实现比较大小的方法:出现频率越低认为优先级越高。
  • 编写优先队列测试类,设置汉字出现的次数,验证汉字出现频率越低的最先出队。
  • 编写成语汉字统计主程序:
    – 读取四字成语的文件,形成字符串;
    – 将字符串转换成汉字数组,通过HashMap统计汉字及其出现频率;
    – 将HashMap中每个汉字与出现频率,依次放入优先队列中,若后续放入的汉字频率高于队列优先级最高的汉字频率,则进行替换。
项目结构

在这里插入图片描述

汉字频率的类
/**
 * 使用优先队列统计成语列表中频率出现最高的前五个字--汉字频率的类
 *
 * @author zhuhuix
 * @date 2020-07-01
 */
public class CharFrequency implements Comparable<CharFrequency> {

    private char c;
    private int frequency;

    CharFrequency(char c, int frequency) {
        this.c = c;
        this.frequency = frequency;
    }

    // 频率低则顺序靠前,优先级最高
    @Override
    public int compareTo(CharFrequency o) {
        if (this.frequency < o.frequency) {
            return 1;
        } else if (this.frequency > o.frequency) {
            return -1;
        } else {
            return 0;
        }
    }

    public char getC() {
        return c;
    }

    public void setC(char c) {
        this.c = c;
    }

    public int getFrequency() {
        return frequency;
    }

    public void setFrequency(int frequency) {
        this.frequency = frequency;
    }

    @Override
    public String toString() {
        return   c +", 出现频率=" + frequency;
    }
}

优先队列测试类
/**
 * 优先队列测试类--频率越低,优先级最高
 * 
 * @author zhuhuix
 * @date 2020-07-01
 */
public class PriorityQueueTest {
    public static void main(String[] args) {

        PriorityQueue<CharFrequency> priorityQueue = new PriorityQueue<>();

        // 将汉字及出现频率放入优先队列
        priorityQueue.enqueue(new CharFrequency('二',2));
        priorityQueue.enqueue(new CharFrequency('五',5));
        priorityQueue.enqueue(new CharFrequency('三',3));
        priorityQueue.enqueue(new CharFrequency('四',4));
        priorityQueue.enqueue(new CharFrequency('一',1));

        // 测试输出
        System.out.println(priorityQueue.dequeue());
        System.out.println(priorityQueue.dequeue());
        System.out.println(priorityQueue.dequeue());
        System.out.println(priorityQueue.dequeue());
        System.out.println(priorityQueue.dequeue());
        
    }
}

在这里插入图片描述

成语汉字统计主程序
/**
 * 使用优先队列统计成语列表中频率出现最高的前五个汉字
 *
 * @author zhuhuix
 * @date 2020-07-01
 */
public class IdiomFreqCount {
    public final static int count = 5;

    public static void main(String[] args) throws IOException {

        // 读取硬盘上的四字成语文件载入字符串对象中
        InputStreamReader inputStreamReader = new InputStreamReader(new FileInputStream("c:\\四字成语.txt"), "GBK");
        BufferedReader bufferedReader = new BufferedReader(inputStreamReader);
        StringBuilder stringBuilder = new StringBuilder();
        String idiom;
        int len = 0;
        while ((idiom = bufferedReader.readLine()) != null) {
            stringBuilder.append(idiom);
            len++;
        }
        bufferedReader.close();
        System.out.println("总共成语" + len + "个");

        // 将字符串对象转换成数组
        char[] array = stringBuilder.toString().toCharArray();

        // 遍历数组中的字符,将字符做为key,出现频率做为value,放入HashMap

        HashMap<Character, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            if (!hashMap.containsKey(array[i])) {
                hashMap.put(array[i], 1);
            } else {
                // 如果字符已存在,则出现次数加1
                hashMap.put(array[i], hashMap.get(array[i]) + 1);
            }
        }
        System.out.println("总共出现汉字" + hashMap.keySet().size() + "个");

        // 根据HashMap中的键与值,构建CharFrequency对象,按CharFrequency的顺序放入优先队列中
        PriorityQueue<CharFrequency> priorityQueue = new PriorityQueue<>();
        for (char key : hashMap.keySet()) {
            // 如果队列中不满统计的字符个数,则直接将对象放入队列中
            if (priorityQueue.getSize() < count) {
                priorityQueue.enqueue(new CharFrequency(key, hashMap.get(key)));
            } else {
                // 如果当前字符的出现频率大于优先队列中排在最前面字符的出现频率,则队列出队并则将该字放入队列中
                // 按此循环,可以使汉字频率出现高的逐渐替换频率出现低的
                if (hashMap.get(key) > priorityQueue.getFront().getFrequency()) {
                    priorityQueue.repalcePriority(new CharFrequency(key, hashMap.get(key)));
                }
            }
        }

        // 依次取出最大堆中的前五个元素,则为出现频率最高的五个字
        int index = Math.min(priorityQueue.getSize(), count);
        for (int i = 0; i < index; i++) {
            System.out.println(priorityQueue.dequeue().toString());
        }
    }

}

  • 输入文件:
    在这里插入图片描述
  • 输出结果:
    在这里插入图片描述

热门文章

暂无图片
编程学习 ·

Spring Boot整合Zookeeper实现配置中心

简介 使用背景 说到配置中心,目前市面上用的较多的配置中心都广为人知,比如百度的Disconf、Spring Cloud Config、携程的Apollo、阿里的Nacos等。由于项目组一直是使用的zookeeper作为配置中心,所以来学习使用。 实现原理在Zookeeper建立一个根节点,比如/CONFIG,代表某个配…
暂无图片
编程学习 ·

自举功能 - 软件复位

说明对于需要长时间运行的电子产品,例如:安防监控等,如果设备程序崩溃后不能自动恢复,可能会出现以下情况:设备操作无反应,用户以为设备坏掉了,并不知道需要断电重启,对产品质量怀疑。 程序崩溃后所有功能中断,有些重要并且需要长时间稳定运行的功能无法延续,例如:定…
暂无图片
编程学习 ·

02 | 该如何选择消息队列?

1.应用场景见: https://blog.csdn.net/william_n/article/details/1040254082.学习/操作2.1 阅读文档02 | 该如何选择消息队列?李玥 2020-01-1400:0013:59讲述:李玥 大小:12.81M你好,我是李玥。这节课我们来聊一下几个比较常见的开源的消息队列中间件。如果你正在做消息队…
暂无图片
编程学习 ·

mysql的语句执行原理详解

需求:select user,host from mysql.user; 以上面的一条命令为例,如何将数据返回的,下面进行详细的阐述:SQL层总结: 语法、语义(数据XX语言)、权限(grant)检查完毕后—> 根据解析器生成解析树—>优化器代价评估—>然后得出执行计划—>执行器执行—>在那…
暂无图片
编程学习 ·

大数据分析的作用有哪些

大数据分析的出现不但可以让老百姓的生活更加便捷,同时也可以提高企业的竞争力,无论是哪个行业以及具体的企业都会有与之对应的大数据分析,而今天就来说说大数据分析对于企业有哪些帮助。数据分析目的1:分类检查未知分类或暂时未知分类的数据,目的是预测数据属于哪个类别或…
暂无图片
编程学习 ·

虚拟机VMware安装学习过程中遇到的几个问题

1.在安装VMware的时候刚开始因为版本不足的原因,电脑显示 Failed to initialize ploicy for cpu 后来我把它复制到百度上发现是我电脑版本过高的原因,于是又下载了VMware15.5.1版本 又查找了它的破解版。2.在安装的过程中还出现过屏幕就一个-,然后什么都不出现,于是查找资…
暂无图片
编程学习 ·

父子组件传值

父子组件传值 子组件要给父组件传值方法,使用$emit 子页面 <template> <div class="testCom"><input type="text" v-model="message" /><button @click="click">发送消息给爸爸</button></div> …
暂无图片
编程学习 ·

linux下安装pip与pip安装

Linux安装pip 参考博客:https://www.cnblogs.com/zhongyehai/p/10619917.html 在执行脚本的时候,说有库找不到:pip安装的时候说不认识pip安装pip 使用脚本安装和升级pip wget https://bootstrap.pypa.io/get-pip.py运行脚本python3 get-pip.py查看版本pip -V如果pip -V,出现…
暂无图片
编程学习 ·

String常用API

这里写目录标题什么是JDK API文档注释规范字符串String以及常用的APIString常量池String常用APIStringBuilderStringBuffer 什么是JDK APIJDK中包含大量打API类库,所谓API(Application Programming Interface,应用程序编程接口)就是一些已写好.可供直接调用的功能(在Java语言中…
暂无图片
编程学习 ·

记录Linux学习2

远程登录到Linux服务器 为什么要远程登录到linux? 因为linux一般是装在机房中,而不是在自己电脑上的,我们需要在公司远程操控Linux系统,所以要远程登录到linux。 Xshell5(远程登录软件),XFtp5(远程上传下载文件的软件) Xshell [1] 是一个强大的安全终端模拟软件,它支…
暂无图片
编程学习 ·

OA、ERP、BPM 各自的功能和特点是什么?怎么配合使用?

​OA是Office Automation的简称,译为办公自动化,常用于企业内部事务管理。OA具有的几个功能:信息存储、数据管理、数据共享。因此,它的使用场景常分布在日常办公中,比如:公文管理、沟通工具、文档管理、项目管理、任务管理、会议管理、通讯录、工作便签、问卷调查、常用工…
暂无图片
编程学习 ·

07:从一个二维数组中查找一个数

题目:从一个二维数组中查找一个数 数组要求:从左到右,从上到小依次递增的矩形二维数组 思路:我们从矩阵的右上角开始查找,若该位置的数值小于目标值,列数减一;若数值大于目标值,行数加一,后续重复。 public class Offer07 {public static void main(String[] args) {i…
暂无图片
编程学习 ·

来啊!快看---redis缓存雪崩,缓存击穿(布隆过滤器),缓存穿透

今天来看看面试中大概率问到的redis三个缓存问题 (缓存雪崩,缓存击穿,缓存穿透) 还是按照常规,来一张期待已久的图片简单说一下上面数据的流程: 当用户发出一个请求,服务器会对其进行解析,然后就是去查找数据啦 第一步去reids缓存查找数据,如果查到想要的数据就返回给…
暂无图片
编程学习 ·

(精品)cesium-绘制动态线(解决闪烁)的进击研究教程

文章目录前因后果效果图先行动态线绘制思路代码及效果图动态线连续绘制思路代码及效果图结论 前因后果 最近项目中,需要绘制墙体,测试了cesium提供的诸多entity,发现都死在了贴纹理阶段;最后妥协于使用wall实体进行墙体的绘制.期间解决了纹理贴图效果,高程遮挡,动态绘制线路闪烁…
暂无图片
编程学习 ·

1. M601 ADC 的使用

1 ADC 相关的数据结构和 API1.1 概论OpenCPU 支持两个模拟输入引脚可用于检测外部电压。请参照管脚定义和ADC 硬件特性。 可以检测的电压范围可分四挡,分别是 1V,2V,3V。本文介绍的数据结构和 API 可以参考 SDK 中 Zyf_adc.h 文件。1.2 用法直接调用 ZYF_AdcRead 接口即可读…
暂无图片
编程学习 ·

AdaBoost算法

AdaBoost算法简介AdaBoost算法的全称是自适应Boosting(Adaptive Boosting),是一种二分类器,它用弱分类器的线性组合构造强分类器。弱分类器的性能不用太好,只需要比随机猜测强,依靠它们可以构造出一个非常准确的强分类器。强分类器的计算公式为:其中x是输入向量,F(x)是…
暂无图片
编程学习 ·

写给跨端玩家:支撑淘宝上亿日活的跨端框架—— Rax 的入门教程(附 TODO Demo)

一些废话沉寂了两个月,我又回来了。跟你们猜的一样,我已经到淘系实习了一段时间了,从上一篇文章之后就放了更多的心思在工作上。上篇文章发出去之后,我去腾讯实习了一段时间,等待阿里实习生入职流程开启。 收到淘系的实习生 offer 后,我买了人生中的第一张机票,第一次坐…