数据结构与算法——堆的应用

简介: 前面说完了堆这种数据结构,并且讲到了它很经典的一个应用:堆排序,其实堆这种数据结构还有其他很多的应用,今天就一起来看看,主要有下列内容:• 优先级队列• 求 Top K 问题• 求中位数

1. 概述


前面说完了堆这种数据结构,并且讲到了它很经典的一个应用:堆排序,其实堆这种数据结构还有其他很多的应用,今天就一起来看看,主要有下列内容:

  • 优先级队列
  • 求 Top K 问题
  • 求中位数


2. 优先级队列


优先级队列是一种特殊的队列,前面学习队列的时候,说到队列满足 先进先出,后进后出 的特点,优先级队列则不是这样。优先级队列中的数据,出队的顺序是有优先级的,优先级高的,先出队列。

而堆其实就可以看作是一个优先级队列,因为堆顶元素总是数据中最大或最小的元素,每次出队列都可以看作取出堆顶元素。

如果你熟悉 Java 语言,则或多或少听说或是使用过 PriorityQueue 这个容器,在《Java 核心技术·卷 I》中,说到 PriorityQueue 就是优先级队列,并且它基于一种很优雅的数据结构——堆。

接下来就小试牛刀,举一个具体的例子来看看优先级队列的应用。例如我们需要合并 10 个有序的小文件,小文件中存储的是有序的字符串数据。借助优先级队列,我们可以很高效的解决这个问题。

我们从每个文件中读取第一个字符串存入优先级队列中,那么每次出队列,都是最小的那个元素。将出队列的数据存储到一个大文件中,然后继续从文件中读取一个字符串存入队列,然后继续出队列,一直循环这个操作。

当然,这主要是针对数据文件较大的情况,如果数据不多,那么直接将全部的数据存入队列,然后依次出队列就可以了,具体问题具体分析。


3. Top K 问题


这样的问题其实非常的常见了,在一组数据当中 ,我们需要求得其前 K 大的数据。

这分为了两种情况,一是针对 静态数据 ,即数据不会发生变化。我们可以维护一个大小为 K 的小顶堆,然后依次遍历数组,如果数组数据比堆顶元素大,则插入到堆中,如果小,则不做处理。遍历完之后,则堆中存在的数据就是 Top K 了。我用代码模拟了这个过程:

public class GetTopK {
    public static void main(String[] args) {
        int[] num = {2, 34, 45, 56, 76, 65, 678, 33, 888, 678, 98, 0, 7};
        //求 Top 3
        Queue<Integer> queue = new PriorityQueue<>(3);
        queue.add(num[0]);
        queue.add(num[1]);
        queue.add(num[2]);
        for (int i = 3; i < num.length; i++) {
            int small = queue.peek();
            if (num[i] > small){
                queue.poll();
                queue.add(num[i]);
            }
        }
        System.out.println(queue.toString());
    }
}


第二种情况,是动态的数据集合,数据会有增加、删除的情况,如果新增一个元素,将其和堆顶元素进行比较,如果数据比堆顶元素大,则插入到堆中,如果小,则不做处理。这样的话,无论数据怎样变化,我们都能够随时拿到 Top K,而不用因为数据的变化重新组织堆。


4. 求中位数


顾名思义,中位数就是一组数据中最中间的那个数据,只不过注意,数据需要有序排列。针对一个大小为 n 的数据集,如果 n 为偶数,那么中位数有两个,分别是 n/2 和 n/2 + 1 这两个数据,我们可以随机取其中一个;如果 n 为奇数,则 n/2 + 1 这个数为中位数。

如果是一个静态的数据,那么可直接排序然后求中位数,但是如果数据有变化,这样每次排序的成本太高了。所以,可以借助堆来实现求中位数的功能。

我们可以维护一个大顶堆,一个小顶堆,小顶堆中存储后 n/2 个数据,大顶堆中存储前面剩余的数据。如果 n 是偶数,则两个堆中存储的都是相同个数的数据,如果 n 为奇数,则大顶堆中要多一个数据。结合下图你就很容易明白了:

如果有数据插入的情况,如果数据小于等于大顶堆顶元素,则插入到大顶堆中,如果数据大于等于小顶堆顶元素,则插入到小顶堆中。只不过可能会出现一个问题,就是堆中的数据不满足均分情况,那么我们需要移动两个堆中的元素,反正需要保证 大顶堆的元素个数和小顶堆的元素个数要么相等,或者大顶堆中多一个。

我用代码简单模拟了整个实现:

public class GetMiddleNum {
        public static void main(String[] args) {
            //原始数据
            Integer[] num = {12, 34, 6, 43, 78, 65, 42, 33, 5, 8};
            //排序后存入ArrayList中
            Arrays.sort(num);
            ArrayList<Integer> data = new ArrayList<>(Arrays.asList(num));
            //大顶堆
            Queue<Integer> bigQueue = new PriorityQueue<>((o1, o2) -> {
                if (o1 <= o2) return 1;
                else return -1;
            });
            //小顶堆
            Queue<Integer> smallQueue = new PriorityQueue<>();
            int n = data.size();
            int i;
            if (n % 2 == 0) i = n / 2;
            else i = n / 2 + 1;
            //后 n/2 的数据存入到小顶堆中
            for (int j = i; j < n; j++) {
                smallQueue.add(data.get(j));
            }
            //前面的数据存入到大顶堆中
目录
打赏
0
0
0
0
2
分享
相关文章
基于 C++ 语言的迪杰斯特拉算法在局域网计算机管理中的应用剖析
在局域网计算机管理中,迪杰斯特拉算法用于优化网络路径、分配资源和定位故障节点,确保高效稳定的网络环境。该算法通过计算最短路径,提升数据传输速率与稳定性,实现负载均衡并快速排除故障。C++代码示例展示了其在网络模拟中的应用,为企业信息化建设提供有力支持。
119 15
监控局域网其他电脑:Go 语言迪杰斯特拉算法的高效应用
在信息化时代,监控局域网成为网络管理与安全防护的关键需求。本文探讨了迪杰斯特拉(Dijkstra)算法在监控局域网中的应用,通过计算最短路径优化数据传输和故障检测。文中提供了使用Go语言实现的代码例程,展示了如何高效地进行网络监控,确保局域网的稳定运行和数据安全。迪杰斯特拉算法能减少传输延迟和带宽消耗,及时发现并处理网络故障,适用于复杂网络环境下的管理和维护。
MapReduce在实现PageRank算法中的应用
总结来说,在实现PageRank算法时使用MapReduce能够有效地进行大规模并行计算,并且具有良好的容错性和可扩展性。
181 76
公司局域网管理视域下 Node.js 图算法的深度应用研究:拓扑结构建模与流量优化策略探析
本文探讨了图论算法在公司局域网管理中的应用,针对设备互联复杂、流量调度低效及安全监控困难等问题,提出基于图论的解决方案。通过节点与边建模局域网拓扑结构,利用DFS/BFS实现设备快速发现,Dijkstra算法优化流量路径,社区检测算法识别安全风险。结合WorkWin软件实例,展示了算法在设备管理、流量调度与安全监控中的价值,为智能化局域网管理提供了理论与实践指导。
88 3
基于 C# 时间轮算法的控制局域网上网时间与实践应用
在数字化办公与教育环境中,局域网作为内部网络通信的核心基础设施,其精细化管理水平直接影响网络资源的合理配置与使用效能。对局域网用户上网时间的有效管控,已成为企业、教育机构等组织的重要管理需求。这一需求不仅旨在提升员工工作效率、规范学生网络使用行为,更是优化网络带宽资源分配的关键举措。时间轮算法作为一种经典的定时任务管理机制,在局域网用户上网时间管控场景中展现出显著的技术优势。本文将系统阐述时间轮算法的核心原理,并基于 C# 编程语言提供具体实现方案,以期深入剖析该算法在局域网管理中的应用逻辑与实践价值。
59 5
论上网限制软件中 Python 动态衰减权重算法于行为管控领域的创新性应用
在网络安全与行为管理的学术语境中,上网限制软件面临着精准识别并管控用户不合规网络请求的复杂任务。传统的基于静态规则库或固定阈值的策略,在实践中暴露出较高的误判率与较差的动态适应性。本研究引入一种基于 “动态衰减权重算法” 的优化策略,融合时间序列分析与权重衰减机制,旨在显著提升上网限制软件的实时决策效能。
72 2
公司员工电脑监控软件剖析:PHP 布隆过滤器算法的应用与效能探究
在数字化办公的浪潮下,公司员工电脑监控软件成为企业管理的重要工具,它能够帮助企业了解员工的工作状态、保障数据安全以及提升工作效率。然而,随着监控数据量的不断增长,如何高效地处理和查询这些数据成为了关键问题。布隆过滤器(Bloom Filter)作为一种高效的概率型数据结构,在公司员工电脑监控软件中展现出独特的优势,本文将深入探讨 PHP 语言实现的布隆过滤器算法在该软件中的应用。
73 1
通过Milvus内置Sparse-BM25算法进行全文检索并将混合检索应用于RAG系统
阿里云向量检索服务Milvus 2.5版本在全文检索、关键词匹配以及混合检索(Hybrid Search)方面实现了显著的增强,在多模态检索、RAG等多场景中检索结果能够兼顾召回率与精确性。本文将详细介绍如何利用 Milvus 2.5 版本实现这些功能,并阐述其在RAG 应用的 Retrieve 阶段的最佳实践。
通过Milvus内置Sparse-BM25算法进行全文检索并将混合检索应用于RAG系统
基于 PHP 语言的滑动窗口频率统计算法在公司局域网监控电脑日志分析中的应用研究
在当代企业网络架构中,公司局域网监控电脑系统需实时处理海量终端设备产生的连接日志。每台设备平均每分钟生成 3 至 5 条网络请求记录,这对监控系统的数据处理能力提出了极高要求。传统关系型数据库在应对这种高频写入场景时,性能往往难以令人满意。故而,引入特定的内存数据结构与优化算法成为必然选择。
97 3
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等