- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
大家好,我是蓝胖子,我一直相信编程是一门实践性的技术,其中算法也不例外,初学者可能往往对它可望而不可及,觉得很难,学了又忘,忘其实是由于没有真正搞懂算法的应用场景,所以我准备出一个系列,囊括我们在日常开发中常用的算法,并结合实际的应用场景,真正的感受算法的魅力.
今天我们就来看看堆这种数据结构.
源码已经上传到github 。
https://github.com/HobbyBear/codelearning/tree/master/heap
在详细介绍堆之前,先来看一种场景,很多时候我们并不需要对所有元素进行排序,而只需要取其中前topN的元素,这样的情况如果按性能较好的排序算法,比如归并或者快排需要n*log( n)的时间复杂度,n为数据总量,排好序后取出前N条数据,而如果用堆这种数据结构则可以在n*log(N)的时间复杂度内找到这N条数据,N的数据量远远小于数据总量n.
接着我们来看看堆的定义和性质,堆是一种树状结构,且分为最小堆和最大堆,最大堆的性质有父节点大于左右子节点,最小堆的性质则是父节点小于左右子节点。如下图所示
并且堆是一颗完全二叉树,完全二叉树的定义如下
若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。
因为结点都集中在左侧,所以我们可以从上到下,从左到右对堆中节点进行标号,如下图所示
从0开始对堆中节点进行标号后,可以得到以下规律
父节点标号 = (子节点标号-1)/2
左节点标号 = 父节点标号 *2 + 1
右节点标号 = 父节点标号 *2 + 2
有了标号和父子节点的标号间的关系,我们可以用一个数组来保存堆这种数据结构,下面以构建一个最大堆为例,介绍两种构建堆的方式.
heapInsert的方式是从零开始,逐个往堆中插入数组中的元素,并不断调整新的节点,让新节点的父节点满足最大堆父节点大于其子节点的性质,这个调整的过程被称作ShiftUp。当数组中元素全部插入完成时,就构建了一个最大堆。代码如下
func HeapInsert(arr []int) *Heap {
h := &Heap{arr: make([]int, 0, len(arr))}
for _, num := range arr {
h.Insert(num)
}
return h
}
heapify的方式是假设数组已经是一个完全二叉树了,然后找到树中的最后一个非叶子节点,然后通过比较它与其子节点的大小关系,让其满足最大堆的父节点大于其子节点的性质,这样的操作被称作ShifDown,对每个非叶子节点都执行ShifDown操作,直至根节点,这样就达到了将一个普通数组变成一个堆的目的.
如果堆的长度是n,那么最后一个非叶子节点是 n/2 -1 ,所以可以写出如下逻辑.
func Heapify(arr []int) *Heap {
h := &Heap{arr: arr}
lastNotLeaf := len(arr)/ 2 -1
for i:= lastNotLeaf;i >= 0; i-- {
h.ShiftDown(i)
}
return h
}
取出根节点的逻辑比较容易,将根节点结果保存,之后让它与堆中最后一个节点交换位置,然后从索引0开始进行ShiftDown操作,就又能让整个数组变成一个堆了.
func (h *Heap) Pop() int {
num := h.arr[0]
swap(h.arr, 0, len(h.arr)-1)
h.arr = h.arr[:len(h.arr)-1]
h.ShiftDown(0)
return num
}
下面我将shiftUp和shiftDown的源码展示出来,它们都是一个递归操作,因为在每次shiftUp或者shiftDown成功后,其父节点或者子节点还要继续执行shifUp或shiftDown操作.
// 从标号为index的节点开始做shifUp操作
func (h *Heap) ShiftUp(index int) {
if index == 0 {
return
}
parent := (index - 1) / 2
if h.arr[parent] < h.arr[index] {
swap(h.arr, parent, index)
h.ShiftUp(parent)
}
}
// 从标号为index的节点开始做shifDown操作
func (h *Heap) ShiftDown(index int) {
left := index*2 + 1
right := index*2 + 2
if left < len(h.arr) && right < len(h.arr) {
if h.arr[left] >= h.arr[right] && h.arr[left] > h.arr[index] {
swap(h.arr, left, index)
h.ShiftDown(left)
}
if h.arr[right] > h.arr[left] && h.arr[right] > h.arr[index] {
swap(h.arr, right, index)
h.ShiftDown(right)
}
}
if left >= len(h.arr) {
return
}
if right >= len(h.arr) {
if h.arr[left] > h.arr[index] {
swap(h.arr, left, index)
h.ShiftDown(left)
}
}
}
最后此篇关于堆的原理以及实现O(lgn)的文章就讲到这里了,如果你想了解更多关于堆的原理以及实现O(lgn)的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
背景: 我最近一直在使用 JPA,我为相当大的关系数据库项目生成持久层的轻松程度给我留下了深刻的印象。 我们公司使用大量非 SQL 数据库,特别是面向列的数据库。我对可能对这些数据库使用 JPA 有一
我已经在我的 maven pom 中添加了这些构建配置,因为我希望将 Apache Solr 依赖项与 Jar 捆绑在一起。否则我得到了 SolarServerException: ClassNotF
interface ITurtle { void Fight(); void EatPizza(); } interface ILeonardo : ITurtle {
我希望可用于 Java 的对象/关系映射 (ORM) 工具之一能够满足这些要求: 使用 JPA 或 native SQL 查询获取大量行并将其作为实体对象返回。 允许在行(实体)中进行迭代,并在对当前
好像没有,因为我有实现From for 的代码, 我可以转换 A到 B与 .into() , 但同样的事情不适用于 Vec .into()一个Vec . 要么我搞砸了阻止实现派生的事情,要么这不应该发
在 C# 中,如果 A 实现 IX 并且 B 继承自 A ,是否必然遵循 B 实现 IX?如果是,是因为 LSP 吗?之间有什么区别吗: 1. Interface IX; Class A : IX;
就目前而言,这个问题不适合我们的问答形式。我们希望答案得到事实、引用资料或专业知识的支持,但这个问题可能会引发辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开,visit the
我正在阅读标准haskell库的(^)的实现代码: (^) :: (Num a, Integral b) => a -> b -> a x0 ^ y0 | y0 a -> b ->a expo x0
我将把国际象棋游戏表示为 C++ 结构。我认为,最好的选择是树结构(因为在每个深度我们都有几个可能的移动)。 这是一个好的方法吗? struct TreeElement{ SomeMoveType
我正在为用户名数据库实现字符串匹配算法。我的方法采用现有的用户名数据库和用户想要的新用户名,然后检查用户名是否已被占用。如果采用该方法,则该方法应该返回带有数据库中未采用的数字的用户名。 例子: “贾
我正在尝试实现 Breadth-first search algorithm , 为了找到两个顶点之间的最短距离。我开发了一个 Queue 对象来保存和检索对象,并且我有一个二维数组来保存两个给定顶点
我目前正在 ika 中开发我的 Python 游戏,它使用 python 2.5 我决定为 AI 使用 A* 寻路。然而,我发现它对我的需要来说太慢了(3-4 个敌人可能会落后于游戏,但我想供应 4-
我正在寻找 Kademlia 的开源实现C/C++ 中的分布式哈希表。它必须是轻量级和跨平台的(win/linux/mac)。 它必须能够将信息发布到 DHT 并检索它。 最佳答案 OpenDHT是
我在一本书中读到这一行:-“当我们要求 C++ 实现运行程序时,它会通过调用此函数来实现。” 而且我想知道“C++ 实现”是什么意思或具体是什么。帮忙!? 最佳答案 “C++ 实现”是指编译器加上链接
我正在尝试使用分支定界的 C++ 实现这个背包问题。此网站上有一个 Java 版本:Implementing branch and bound for knapsack 我试图让我的 C++ 版本打印
在很多情况下,我需要在 C# 中访问合适的哈希算法,从重写 GetHashCode 到对数据执行快速比较/查找。 我发现 FNV 哈希是一种非常简单/好/快速的哈希算法。但是,我从未见过 C# 实现的
目录 LRU缓存替换策略 核心思想 不适用场景 算法基本实现 算法优化
1. 绪论 在前面文章中提到 空间直角坐标系相互转换 ,测绘坐标转换时,一般涉及到的情况是:两个直角坐标系的小角度转换。这个就是我们经常在测绘数据处理中,WGS-84坐标系、54北京坐标系
在软件开发过程中,有时候我们需要定时地检查数据库中的数据,并在发现新增数据时触发一个动作。为了实现这个需求,我们在 .Net 7 下进行一次简单的演示. PeriodicTimer .
二分查找 二分查找算法,说白了就是在有序的数组里面给予一个存在数组里面的值key,然后将其先和数组中间的比较,如果key大于中间值,进行下一次mid后面的比较,直到找到相等的,就可以得到它的位置。
我是一名优秀的程序员,十分优秀!