[Algorithm] How to use Max Heap to maintain K smallest items
to How use max ALGORITHM Heap items Smallest
2023-09-14 08:59:15 时间
Let's say we are given an array:
[4,1,5,2,3,0,10]
We want to get K = 3 smallest items from the array and using Max heap data structure.
So this is how to think about it.
1. We take first K items put it into Max Heap:
5
/ \
4 1
2. Then we move forward to next element '2' in the array, we check
- Whether 2 is smaller than current max item in heap, which is '5', if yes, then replace 5 with 2
- Then re-arrange the heap
4
/ \
2 1
3. Repeat the process for items [3,0]
3 2
/ \ / \
2 1 0 1
4. When the item is '10' which is larger than current max '2', we just ingore it.
5. In the end, we got K smallest items, we just need to print it out. (K smallest items are not ncessary in order)
相关文章
- list遍历的几种方式_arraylist cannot be cast to
- What is /dev/null and How to Use It
- django raw_id_fields 显示名称而不是id(raw_id_fields: How to show a name instead of id)
- How to Use the Stdin, Stderr, and Stdout Streams in Bash
- ORA-01366: failed to find redo logs required for terminal apply ORACLE 报错 故障修复 远程处理
- ORA-24397: error occured while trying to free connections ORACLE 报错 故障修复 远程处理
- ORA-28393: password required to close the wallet ORACLE 报错 故障修复 远程处理
- ORA-28582: a direct connection to this agent is not allowed ORACLE 报错 故障修复 远程处理
- ORA-38426: attribute set assigned to an expression set may not be dropped ORACLE 报错 故障修复 远程处理
- ORA-39117: Type needed to create table is not included in this operation. Failing sql is: string ORACLE 报错 故障修复 远程处理
- postgresql 数据库中 to_char()常用操作介绍
- ECC TO HANA FAGLB03 search-help on Account Number field doesn’t working or not returning the selected value to the Account Number field.详解编程语言
- How to use ‘Goto statement’ to do backward debugging in ABAP 详解编程语言
- How to validate RFC connection in SAP详解编程语言
- 的安装How to Install Linux English Language Pack(linux英文语言包)
- Oracle主键生成技巧详解how to generate primary key in Oracle(oracle主键生成)
- Linux崩溃?如何应对与解决(Crash Linux: How to Handle and Fix)(crashlinux)
- Maximizing Efficiency: How to Optimize Your Workflow with SSH Linux Tools(sshlinux工具)
- How to Compile Redis from Source Code: A StepbyStep Guide(redis源码编译)
- How to Mount Fibre Channel Storage in Linux for Efficient Data Management(linux挂载光纤存储)
- Exploring the World of MySQL: Understanding How to Query the Current Database(mysql查询当前库)
- Installing QQ on Linux: A Guide to Getting Started(linux下安装qq)
- Maximizing Performance: How to Easily Monitor and Optimize Your Oracle SGA.(oracle查看sga)
- 如何使用Redis查看键的过期时间?How to use Redis to view the expiration time of a key?(redis查看过期时间)
- Efficient MySQL Queries: How to Retrieve Partial Data Fields.(mysql查询部分字段)
- Troubleshooting Oracle Login Issues: How to Fix User Login Failures(oracle用户登录不了)
- Learn How to Set IP using Linux and C: The Ultimate Guide(linuxc设置ip)
- StepbyStep Guide to Configuring a Network Bridge on Linux Systems(linux系统下配置网桥)